FPS24 A - お菓子

求めるものは$ (x+x^3+x^4+x^6)^D [x^N] である。sparseな多項式の累乗をライブラリに持っていればそれで殴れば $ O(N) で解ける。exp-logを使った累乗だと遅くて通らなかった。

$ x+x^3+x^4+x^6=x(1+x^2+x^3(1+x^2))=x(1+x^2)(1+x^3)より、$ (1+x^2)^D の展開を考え $ x^{2j} の係数と $ (1+x^3)^Dの $ x^{\frac{N-D-2j}{3}} の係数をそれぞれ掛けたものを足し合わせればよいことがわかる。その係数は二項定理より直ちに従う。