問題
https://atcoder.jp/contests/arc140/tasks/arc140_f
解説
公式解説では [x^N] (x+2x^2+2x^3+...)^K を 1<=K<=N について求めよというパートが出てきてここでダブリングをしていますが、別の方法を紹介します。
Kを固定してみると、求めたい値は
[x^(N-K)] (1+2x+2x^2+...)^K
= [x^(N-K)] ( (1+x) / (1-x) )^K
= [x^(N-K)] (2/(1-x)-1)^K
となり、ここを二項定理でバラして K - i = j とすると、
(分子) = 2^i * (-1)^j * (N-j-1)! * (i+j)!
(分母) = (N-(i+j))! * (i-1)! * i! * j!
になって畳み込めるので、そうすると高速になります。
実装 (fastest)
https://atcoder.jp/contests/arc140/submissions/43458503
質問
[x^N] f(x)^K を K=1,2,...,について求める系って一般的ななんかうまいやり方ありますか？
