AtCoder Grand Contest 001 E - BBQ Hard

天才か…

問題

agc001.contest.atcoder.jp

解法

普通に計算しようとすると,

(Ai + Aj + Bi + Bj)! / (Ai+Aj)! / (Bi+Bj)!

を各 i, j について求めてその和を計算することになります。が, これだと間に合いません。

そこで, 上の式をよく見ると, これは (0, 0) から (Ai+Aj, Bi+Bj) へ向かう経路の場合の数になっていることに気付きます。対称性的なものを意識すると, (-Aj, -Bj) から (Ai, Bi) に向かう場合の数にもなっています。こう考えることができると勝ちで, スタート地点を (-A1, -B1), ..., (-AN, -BN) のいずれかとして ゴールを (A1, B1), ..., (AN, BN) のいずれかとする場合の数を求めれば良いです。

ただ, これだと (i < j) の組についてか考慮しないというのを無視しています。そのために, X = ( (-Ai, -Bi) から (Ai, Bi) へ向かう経路の数の和 ) というのを求めて, 上記の総和から引いたのち, 2 で割れば良いです。

1 個目のアイデアは天才的だけど 2 つ目のはたまによく見るので思いつけないとダメですね。

const int MAXN = 200200;
const int MAXM = 2022;
const int MOD = 1e9 + 7;
const int inv2 = 5e8 + 4;
int A[MAXN], B[MAXN];

ll fact[4 * MAXM], rfact[4 * MAXM];
ll dp[2 * MAXM][2 * MAXM];

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, m-2, m);
}

ll nCr(int n, int r) {
	return fact[n] * rfact[r] % MOD * rfact[n - r]%MOD;
}

int main() {
	fact[0] = rfact[0] = 1;
	for (int i = 1; i < 4 * MAXM; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		rfact[i] = mod_inverse(fact[i], MOD);
	}
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		dp[MAXM - A[i]][MAXM - B[i]] += 1;
	}
	for (int x = 1; x < 2 * MAXM; x++) for (int y = 1; y < 2 * MAXM; y++) {
		dp[x][y] += dp[x - 1][y] + dp[x][y - 1];
		dp[x][y] %= MOD;
	}
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		(ans += dp[MAXM + A[i]][MAXM + B[i]]) %= MOD;
		(ans -= nCr(2 * A[i] + 2 * B[i], 2 * A[i])) %= MOD;
		if (ans < 0) ans += MOD;
	}
	(ans *= inv2) %= MOD;
	cout << ans << endl;
	return 0;
}

計算式が格子点の経路になっていることを深く考えれば思いついた…かも？(難しい)