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

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)$

那么就是一个多项式求逆的模板了