好像是多项式最基础的算法（？，但是咕了比较久，现在学一下吧。
差值是啥
这个东西类似于 FFT 的转化过程，就是多项式点值和多项式系数的转化，简而言之就是解决下面的问题，P4781。
已知一个 /(n-1/) 次多项式的 /(n/) 个点值，/(f(x_i)=y_i/)，已知 /(k/)，求 /(f(k)/bmod 998244353/)。
/(n/le 2000/)
咋做
显然可以直接列方程然后高斯消元，复杂度 /(O(n^3)/)，非常寻宝。
考虑一个构造，令 /(F(x)=/sum f_i(x)/frac{y_i}{f_i(x_i)}/)，其中 /(f_i(x)/) 是一个和 /(x_i/) 有关的多项式，满足 /(f_i(x_i)/ne 0,f_i(x_j)=0(j/ne i)/)，这样就可以满足 /(F(x_i)=y_i/) 了，因为其他项全都是 /(0/)。
再考虑怎么去构造这个 /(f_i(x)/)。
因为显然 /(x_i/) 互不相同，所以可以构造出：
/[f_i(x)=/prod_{j/ne i}(x-x_j)
/]
最后整理一下，可以得到：
/[F(k)=/sum_{i=1}^n y_i /frac{/prod_{j/ne i}(k-x_j)}{/prod_{j/ne i} (x_i-x_j)}
/]
直接计算，时间复杂度 /(O(n^2)/)。
- 点值连续差值
上面部分相当于一个前缀乘上一个后缀可以直接预处理，下面部分相当于每次一个阶乘乘上一些 /(-1/)，可以列出：
/[F(k)=/sum_{i=1}^n y_i /frac{/prod_{j/ne i}(k-x_j)}{(i-1)!(n-i)!(-1)^{i-1}}
/]
时间复杂度 /(O(n)/)。
原创文章，作者：745907710，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/271744.html