题解 P4721 【【模板】分治 FFT】

nekko

2018-07-02 14:53:44

Solution

~~不太严谨+也许漏洞百出的题解~~ 已知$\{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)$ 那么就是一个多项式求逆的模板了