二項係数に帰着。実装も考察も楽だと思う
問題
日本語なので省略。
https://atcoder.jp/contests/aising2020/tasks/aising2020_f
解法
まず、問題を次のように言い換える。
すぬけ君は整数$$ 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 \] 最後に、分子を展開すれば、 \[ \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}}$$のある項の係数を高速に求めることができればよい。これは実際1つの二項係数で表すことができ、$$\displaystyle \frac{1}{(1-x^{2})^{16}}$$の$$x^{2k}$$の係数は、$$ \displaystyle \binom{ k+15 }{ 15 } $$となる。(パスカルの三角形を斜めに切っていくイメージ)
