Codeforces Round #419 (Div. 1): B. Karen and Test

,

九条カレンちゃん回だった。ratingは$+54$して$2146$で王手。

solution

線形性。実験。$N \equiv 1 \mod 4$のときがとても綺麗な形になるので、高々$3$回愚直にやったあと規則性。$O(N \log N)$。

長さ$N$の数列$a = ( a_i )_{i \lt N}$を処理するが操作は全て線形。 数列$e_i$を$i$番目の項だけ$1$でそれ以外$0$な列とすると、答え$f(a) = \sum_{i \lt N} a_i f(e_i)$となる。 このような入力$e_i$に関して実験する。 $N \equiv 1 \mod 4$のとき、$0$-basedで奇数番目の$f(e_i) = 0$、偶数$2i$番目なら$f(e_i) = {}_{N/2}C_{i/2}$が分かる。 よって$O(N \log N)$。

implementation

#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) { // p must be a prime, O(log p)
    assert ((x % p + p) % p != 0);
    return powmod(x, p-2, p);
}
template <int mod>
int fact(int n) {
    static vector<int> memo(1,1);
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n+1);
        repeat_from (i,l,n+1) memo[i] = memo[i-1] *(ll) i % mod;
    }
    return memo[n];
}
template <int mod>
int choose(int n, int r) { // O(n) at first time, otherwise O(\log n)
    if (n < r) return 0;
    r = min(r, n - r);
    return fact<mod>(n) *(ll) inv(fact<mod>(n-r), mod) % mod *(ll) inv(fact<mod>(r), mod) % mod;
}

constexpr int mod = 1e9+7;
int main() {
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    {
        int op = +1;
        while (n % 4 != 1) {
            vector<int> b(n-1);
            repeat (i, n-1) {
                b[i] = (a[i] + op * a[i+1] +(ll) mod) % mod;
                op *= -1;
            }
            -- n;
            a = move(b);
        }
        assert (a.size() == n);
    }
    ll result = 0;
    repeat (i, n/2+1) {
        result += a[2*i] *(ll) choose<mod>(n/2, i) % mod;
    }
    result %= mod;
    printf("%lld\n", result);
    return 0;
}