题解 P4721 【【模板】分治 FFT】
nekko
2018-07-02 14:53:44
~~不太严谨+也许漏洞百出的题解~~
已知$\{g_{i} | i \in [1,n-1] \cap Z\}$,且$f_0=1$,同时有$f_i=\sum_{j=1}^{i}f_{i-j}g_j$
求$\{ f_i | i \in [0,n - 1] \cap Z \}$
---
不妨设$F(x)=\sum_{i=0}^{\infty}f_ix^i,G(x)=\sum_{i=0}^{\infty}g_ix^i$,且$g_0=0$
那么有$F(x)G(x)=\sum_{i=0}^{\infty}x^i\sum_{j+k=i}f_jg_k=F(x)-f_0x^0$
即$F(x)G(x) \equiv F(x)-f_0 (\bmod x^n)$
即$F(x) \equiv \frac{f_0}{1-G(x)} (\bmod x^n)$
即$F(X) \equiv (1-G(x))^{-1} (\bmod x^n)$
那么就是一个多项式求逆的模板了