http://codeforces.com/contest/815/problem/B
手を動かすのは大事ですね…
実験すると4周期ごとにパスカルの三角形が出てくることに気づく。
int N; ll A[MAX_N]; ll F[MAX_N]; ll D[10][10]; bool sign[10][10]; ll mod_pow(ll a, ll n) { if(n == 0) return 1; ll res = mod_pow(a, n / 2); if(n % 2 == 0) return res * res % MOD; else return a * res % MOD * res % MOD; } ll inv(ll a) { return mod_pow(a, MOD - 2); } ll C(int a, int b) { return F[a] * inv(F[b]) % MOD * inv(F[a - b]) % MOD; } void solve() { cin >> N; F[0] = 1; rep(i, 0, N) { cin >> A[i]; F[i + 1] = F[i] * (i + 1) % MOD; } int n = (N - 1) / 4 * 4; rep(i, 0, N) { rep(j, 0, 4) { if(i - j < 0 || ((i - j) % 2)) continue; ADD(D[0][j], (C(n / 2, (i - j) / 2) * A[i] % MOD)); } } //debug(vector<int>(D[0], D[0] + 4)); int cnt = 0; rep(i, 0, 4) { sign[i][0] = cnt % 2; rep(j, 1, 4) { sign[i][j] = 1 - sign[i][j - 1]; } cnt += N - i - 1; } rep(i, 0, 4) { rep(j, 0, 3 - i) { if(!sign[i][j]) D[i + 1][j] = (D[i][j] + D[i][j + 1]) % MOD; else D[i + 1][j] = (D[i][j] - D[i][j + 1] + MOD) % MOD; } //debug(vector<int>(D[i], D[i] + 4)); } cout << D[N - 1 - n][0] << "\n"; }
久しぶりに逆元使ったのでバグらせまくった。