E - Stop. Otherwise... | AtCoder Regular Contest 102

包除原理とド・モルガンの法則使って求めるやつ。

包除原理 - Wikipedia

六面サイコロを考える。つまりK=6として、出目の和が7になるペアは(1, 6), (2, 5), (3, 4)の3種類。これらのペアが一つもできない場合を求めたい。すべての出目の組をUとし、それぞれのペアができてしまう出目の組をそれぞれA, B, Cとすると求めるのは以下。 
n(\overline{A} \cap \overline{B} \cap \overline{C})\\
= n(\overline{A \cup B \cup C})\\
= n(U)-n(A \cup B \cup C)\\
= n(U)-(n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C))\\
=n(U)-(n(A)+n(B)+n(C))+(n(A\cap B)+n(B\cap C)+n(C\cap A))-n(A\cap B\cap C)\\
=\sum_{i=3}^{3}(-1)^{i}f(i)

fは適当な関数。ここで特にf(0)=n(U)としているのに注意。一般にペアがm種類あるとき、 
\sum_{i=0}^{m}(-1)^{i}f(i)
を求めればよい。

あとはf(i)の求め方を考える。上式の各項のi個のペアの作り方はC(m, i)通り。その一通りに対して、残りのN-2i個のサイコロの目の出方はどれでもよく、H(K, N-2i)通り。よって 
f(i)=C(m, i)*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;
}