E - Stop. Otherwise... | AtCoder Regular Contest 102
包除原理とド・モルガンの法則使って求めるやつ。
六面サイコロを考える。つまりK=6として、出目の和が7になるペアは(1, 6), (2, 5), (3, 4)の3種類。これらのペアが一つもできない場合を求めたい。すべての出目の組をUとし、それぞれのペアができてしまう出目の組をそれぞれA, B, Cとすると求めるのは以下。
fは適当な関数。ここで特にf(0)=n(U)としているのに注意。一般にペアがm種類あるとき、 を求めればよい。
あとはf(i)の求め方を考える。上式の各項のi個のペアの作り方はC(m, i)通り。その一通りに対して、残りのN-2i個のサイコロの目の出方はどれでもよく、H(K, N-2i)通り。よって
int K, N; cin >> K >> N; for (int i = 2; i <= 2 * K; ++i) { int ps = min(K, i / 2) - max(1, i - K) + 1; mint ans = 0; for (int j = 0; j <= min(N/2, ps); ++j) { mint x = comb::C(ps, j) * comb::H(K, N - 2 * j); ans += x * (j % 2 ? -1 : 1); } cout << ans << endl; }