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

http://codeforces.com/contest/815/problem/B

解法

和の線形性（重ね合わせの原理）を用いて計算するとうまくいく。

i 番目の要素以外を 0 として、i 番目の要素が与える影響を調べてみることにする。

動的計画法により結果を得ることができるが、それでは O(n^2) であり間に合わない。よく見ると、この動的計画法の形はグリッドグラフにおける最短経路数を求める DP の形によく似ている。

適当な位置でグリッドを切り出してみよう。右下に降りるのを右移動に対応させ、左下に降りるのを下移動に対応させている。

規則的に 0 が現れるので、0 を削除してみる。

よって二項係数で各位置の値が求まることが分かるだろう。符号の並び方で 4 パターンのグリッドが存在するが、頑張るとなんとかなる。

二項係数で求まることはすぐ分かったんだけど、微妙なところを詰めるのに妙に時間がかかった。というか詰めきれてなくてコードがかなり汚い（他の人のコードを見た方がいい）。

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

int dp[50][50];

constexpr int MOD = 1e9 + 7;

struct modint {
	int n;
	modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= MOD ? a.n - MOD : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + MOD : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % MOD); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

class Combination {
public:
	Combination() {
		inv.push_back(0);
		inv.push_back(1);
		f.push_back(1);
		f.push_back(1);
		invf.push_back(1);
		invf.push_back(1);
	}

	modint F(int n) {
		check(n);
		return f[n];
	}

	modint IF(int n) {
		check(n);
		return invf[n];
	}

	modint inverse(int n) {
		check(n);
		return inv[n];
	}

	modint P(int n, int r) {
		if (n < 0 || r < 0 || n < r) {
			return 0;
		}
		check(n);
		return f[n] * invf[n - r];
	}

	modint C(int n, int r) {
		if (n < 0 || r < 0 || n < r) {
			return 0;
		}
		check(n);
		return f[n] * invf[r] * invf[n - r];
	}

	modint H(int n, int r) {
		if (n == 0 && r == 0) {
			return 1;
		}
		return C(n + r - 1, r);
	}

private:
	std::vector<modint> inv;
	std::vector<modint> f;
	std::vector<modint> invf;

	void check(int k) {
		if (k < inv.size()) {
			return;
		}
		int p = inv.size() - 1;
		inv.resize(k + 1);
		f.resize(k + 1);
		invf.resize(k + 1);
		for (int i = p + 1; i <= k; i++) {
			inv[i] = inv[MOD % i] * (MOD - MOD / i);
			f[i] = i * f[i - 1];
			invf[i] = inv[i] * invf[i - 1];
		}
	}
};

void foo() {
	dp[0][0] = 1;
	for (int i = 0; i < 40; i++) {
		for (int j = 0; j < 40; j++) {
			dp[i][j + 1] += dp[i][j];
			int sgn;
			int k = (i % 4 - j % 4 + 4) % 4;
			if (k == 2 || k == 3) {
				putchar('+');
				sgn = 1;
			} else {
				putchar('-');
				sgn = -1;
			}
			dp[i + 1][j] += dp[i][j] * sgn;
		}
		puts("");
	}

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 40; j++) {
			printf("%4d", dp[i][j]);
		}
		puts("");
	}
}

Combination comb;

modint f(int i, int j, int k) {
	if (i < 0 || j < 0 || j > i) {
		return 0;
	}
	if (i == 0 && j == 0) {
		return 1;
	}

	int k1 = k + i % 2;
	int k2 = k1 + (i + 1) % 2;

	int s1 = (j + k) % 2 != 0 ? 1 : MOD - 1;
	int s2 = (j + 1 + k1) % 2 != 0 ? 1 : MOD - 1;
	int s3 = (j + 2 + k2) % 2 != 0 ? 1 : MOD - 1;

	if (s1 == 1 && s2 == 1 && s3 == MOD - 1) {
		int h = j;
		int w = i - j;
		if (h % 2 == 1 && w % 2 == 1) {
			return 0;
		}
		int sgn = 1;
		if (h % 4 == 1 && w % 4 == 2) {
			sgn = MOD - 1;
		} else if (h % 4 == 3 && w % 4 == 0) {
			sgn = MOD - 1;
		}
		return sgn * comb.C(h / 2 + w / 2, w / 2);
	}
	if (s1 == MOD - 1 && s2 == MOD - 1 && s3 == 1) {
		int h = j;
		int w = i - j;
		if (h % 2 == 1 && w % 2 == 1) {
			return 0;
		}
		int sgn = 1;
		if (h % 4 == 1 && w % 4 == 0) {
			sgn = MOD - 1;
		} else if (h % 4 == 3 && w % 4 == 2) {
			sgn = MOD - 1;
		}
		return sgn * comb.C(h / 2 + w / 2, w / 2);
	}
	return f(i - 1, j, k1) + s1 * f(i - 1, j - 1, k1);
}

int main() {
	int n;
	std::cin >> n;

	std::vector<modint> a(n);
	modint ans;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].n);
		ans += f(n - 1, i, 0) * a[i];
	}
	std::cout << ans.n << std::endl;
}

こういう微妙にずれる系は苦手。