yukicoder No.3046 yukicoderの過去問
問題文
解法
$O(KlogK)$解法
まずは2次元DPを考える。$dp\lbrack i \rbrack \lbrack j \rbrack$を$i$回移動して$j$の位置にいるときの組み合わせの数 とすると、答えは、 $\sum_{i=0}^{\infty} dp\lbrack i \rbrack \lbrack k \rbrack$。
DP配列を多項式とみる。$f(A)=A^{x1}+A^{x2}+ \cdots + A^{xn}$
とすると、$dp_{i+1}(A)=dp_{i}(A) f(A)$となる。さらに、$dp_0(x)=1$より、$dp_{i}(x)=f(x)^i$である。
このようにDPを多項式に置き換えていくと、解は、$\sum_{i=0}^{\infty} f(x)^i$の$x^k$の係数である。
ここで、
\[
\sum_{i=0}^{\infty} f(x)^i = \frac{1}{1-f(x)}
\]
であるから$1−f(x)$の逆元が求まれば良い。逆数はこれで求まるので、$(KlogK)$でこの問題は解ける。