自动搬运

查看原文

来自洛谷，原作者为

	nekko **

搬运于2025-08-24 22:02:58，当前版本为作者最后更新于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)$

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