题解 P5667 【拉格朗日插值2】

· · 题解

由插值公式可得

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