エイシング プログラミング コンテスト 2020 F - Two Snuke
二項係数に帰着。実装も考察も楽だと思う
問題
解法
まず、問題を次のように言い換えます。
すぬけ君が整数$ s, n, u, k, e, \Delta s, \Delta n, \Delta u, \Delta k, \Delta e$を以下の条件をすべて満たすように選んだとき、ありうるすべての組み合わせに対して$\Delta s \Delta n \Delta u \Delta k \Delta e$を足したものを求めよ。
- $ s \ge 0, n \ge 0, u \ge 0, k \ge 0, e \ge 0$
- $ \Delta s > 0,\Delta n > 0,\Delta u > 0,\Delta k > 0,\Delta e > 0$
- $ 2s + 2n + 2u + 2k + 2e + \Delta s + \Delta n + \Delta u + \Delta k + \Delta e = p $
- $ p \le N $
これを次数を$ N $ の値、係数を各$N$に対する答えとした形式的べき級数で表すと、答えは
\[
(1+x ^{2} + x^{4} + x^{6} + \cdots) ^ {5} (x + 2x^{2} + 3x^{3} + 4x^{4} + \cdots) ^ {5} \frac{1}{1-x} \lbrack x^{N} \rbrack
\]
となります。
$s, n, u, k, e$は、1個とると$p$が2ずつ変化するので$1+x ^{2} + x^{4} + x^{6} + \cdots$と対応し、
$\Delta s, \Delta n, \Delta u, \Delta k, \Delta e$は答えが個数倍になり、1個以上選ばなければいけないので$ x + 2x^{2} + 3x^{3} + 4x^{4} + \cdots $と対応します。
4つ目の条件($p$が$N$以下)は、累積和を取る意味で$ \displaystyle \frac{1}{1-x}$と対応します。
この式を計算しやすいように変形します。
\[
1+x ^{2} + x^{4} + x^{6} + \cdots = \frac{1}{1-x^{2}}
\]
と、
\[
x + 2x^{2} + 3x^{3} + 4x^{4} + \cdots = x (1 + 2x + 3x^{2} + 4x^{3} + \cdots) = \frac{x}{(1-x)^{2}}
\]
を使えば、
\[
\frac{1}{(1-x^{2})^{5}} \frac{x^{5}}{(1-x)^{10}} \frac{1}{1-x} [ x^{N} ]
\]
となります。さらに分母と分子に$(1+x)^{11}$をかけると、
\[
\frac{(1+x)^{11}}{(1-x^{2})^{16}} \lbrack x^{N-5} \rbrack
\]
と変形でき、分母に$(1-x^2)$のみ現れるようになりました。
最後に、分子を展開すると、
\[
\sum_{k = 0}^{11} \left( \binom{11}{k} \frac{1}{(1-x^{2})^{16}} \lbrack x^{N-5-k} \rbrack \right)
\]
となります。$\displaystyle \frac{1}{(1-x^{2})^{16}}$の$x^{2k}$の係数は、$ \displaystyle \binom{ k+15 }{ 15 } $となるので、定数時間で答えを求めることができます。