本質的には公式解説と同じはずです．同じ解法を形式的べき級数の式変形により導出します．公式解説で証明なしに紹介していた等式も証明されます．

まず本問の答は次のように表せます：

\[[t^Nx^Xy^Y]\prod_{b=0}^{M-1}\left(1+\frac{t}{1-xy^b}\right).\]

この総積を \(F(t,x,y)\) とします．

\[G(t,x,y)=F(t-1,x,y)=\prod_{b=0}^{M-1}\frac{t-xy^b}{1-xy^b}\]

とします．\(g(t)=[x^Xy^Y]G(t,x,y)\) とすると答は \([t^N]g(t+1)\) となります（\(F\) を \(G\) に取り換えること公式解説における \(f(K)\) を考えることと対応します）．よって \(g(t)\) が求まればよいです．

\[G_1(t,x,y)=\prod_{b=0}^{M-1}(t-xy^b),\qquad G_2(t,x,y)=\prod_{b=0}^{M-1}(1-xy^b)^{-1}\]

とします．求めるべきは \([x^Xy^Y]G_1(t,x,y)G_2(t,x,y)\) です．

\(G_1\) の計算を考えます．まず，\(t,x\) についての \(1\) 次同次式の積なので，\(G_1\) の計算は本質的には \(\prod_{b=0}^{M-1}(1-xy^b)\) の計算と等価です．

\(y=q\) を定数と見なして 1 変数形式的べき級数 \(A(x)=\prod_{b=0}^{M-1}(1-q^bx)\) を考えましょう．この係数を \(A_n\) とおけば，\((1-q^M)A(x)=(1-x)A(qx)\) から係数間の漸化式 \((1-q^nx)A_{n}=(1-q^{M+n-1})A_{n-1}\) が得られます．よって，\(A_n\) は \(\frac{q^{i-1}-q^M}{1-q^i}\) のような式を \(n\) 個かけたものとして得られます． \(B(x)=\prod_{b=0}^{M-1}(1-q^bx)\) の場合も同様で，この場合には \(\frac{1-q^{M+i-1}}{1-q^i}\) のような式の \(n\) 個の積が係数を与えることが分かります．（この \(n\) 個の積を具体的に書き下すと，公式解説にある \(q\) 二項係数になります）

したがって，

• \([x^X]G_1(t,x,y)\) や \([x^X] G_2(t,x,y)\) は \(\frac{y^j-y^k}{1-y^i}\) の形の有理式の積で書ける．
• \(X\) を固定したときに \([x^Xy^i]\) (\(1\leq i\leq Y\)) が \(O(X+Y\log Y)\) 時間で計算できる．また，\([x^Xy^i]\) (\(1\leq i\leq Y\)) から \([x^{X+1}y^i]\) (\(1\leq i\leq Y\)) を計算すること（または \(G_2\) についてはその逆方向の計算）が \(O(Y)\) 時間でできる．

ことが分かります．

\(G_1\) について \(y\) について \(Y\) 次以下の項が存在するのは \(x\leq \sqrt{2Y}\) 程度に限られます．すると \(G_2\) についても興味のある \(x\) の次数の範囲も \(\sqrt{2Y}\) 程度の幅に限定されます．これらの範囲で \(G_1, G_2\) を計算することは上で述べたことから \(O(X+Y^{1.5})\) 時間でできます．

問題全体では \(O(M+Y^{1.5})\) 時間で解けて，適切な計算手順を選べば，空間は線形にもできます．