Codeforces Round #419B: Karen and Test

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";
}

久しぶりに逆元使ったのでバグらせまくった。