ナイーブなdpから直接解法を導きます。

\(F_i(x,y)\)を\(x^ly^s\)に\(A_1=K\)かつ\(A_i=l\)かつ\(\sum A_j=s\)を満たす\((A_1,\dots,A_i)\)に対する\(f(A)\)の総和を持つ\(2\)変数母関数とします。このとき、\(F_{i+1}(x,y)=\displaystyle\sum_{l \geq 0} [ x^l ] F_i(x,y) \sum_{k \geq 0} \binom{k+l}{k} (xy)^k=\sum_{l \geq 0} [ x^l ] F_i(x,y) \frac{1}{(1-xy)^{l+1}}=\frac{1}{1-xy}F_i\left(\frac{1}{1-xy},y\right)\)が成り立ちます。目標は\([ y^M ] F_N(1,y)\)を求めることです。ここで、\(n>0\)について\(x^ny^0\)の係数は\(0\)であることに注意してください。

いま、帰納的に計算することによって、\(g(x)=\frac{1}{1-xy}\)として、\(F_i(1,y)=y^K(g^{i-1}(1))^{K +1}\displaystyle\prod_{j=1}^{i-2} g^j(1)\)と等しいことがわかります。さらに、\(g^j(1)=\frac{1}{1-g^{j-1}(1)y}\)より、帰納的に\(P_0=P_1=1,P_n=P_{n-1}-yP_{n-2}\)を満たす多項式列\(P\)を用いて\(g^j(1)=\frac{P_j}{P_{j+1}}\)と表すことができ、ゆえに和の中抜けから\(F_N(1,y)=y^K\frac{P_{N-1}^K}{P_N^{K+1}}\)と表せます。

\(P_N\)は多項式を行列に乗せる、または実際に線形漸化式を解くことにより\(O(N \log^2 N)\)または\(O(N \log N)\)でできるので、十分高速に解くことができます。