自动搬运

查看原文

来自洛谷，原作者为

	forgottencosecant **

搬运于2025-08-24 22:13:10，当前版本为作者最后更新于2019-11-20 20:36:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

由插值公式可得

$$f(m+x)=\sum_{i=0}^{n}f(i)\prod_{j \neq i}\frac{m+x-j}{i-j}=\sum_{i=0}^{n}f(i) \frac{(m+x)!/(m+x-n-1)!}{(m+x-i)(-1)^{n-i}i!(n-i)!} $$

令

$$u_i=\frac{f(i)}{(-1)^{n-i}i!(n-i)!}$$

当$i>n$时$u_i=0$

$$v_i=\frac{1}{m-n+i}$$

可得

$$(u * v)_{x}=\sum_{i=0}^{x}\frac{f(i)}{(-1)^{n-i}i!(n-i)!(m-n+x-i)} $$$$(u * v)_{n+x}=\sum_{i=0}^{n}\frac{f(i)}{(-1)^{n-i}i!(n-i)!(m+x-i)} $$

即

$$f(m+x)=(u*v)_{n+x}\prod_{i=m+x-n}^{m+x}i$$

于是可用一次NTT求出$f(m),f(m+1),...,f(m+n)$。

总复杂度$O(n \log n)$。