题解 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)

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