拉格朗日插值
基本介绍
- 对于一个 \(n\) 次多项式 \(f(x)=\sum\limits_{i=0}^nf_ix^i\)，给出其 \(n+1\) 个位置上的值，即 \(\forall 1\leq i\leq n+1,f(x_i)=y_i\)，你需要对于给定的 \(X\)，求出 \(f(X)\) 的值。
仿照中国剩余定理，构造 \(g_i(x)\) 使得 \(g_i(x_j)=[i=j]\)，具体构造为 $$g_i(x)=\prod\limits_{j\neq i}\frac{x-x_j}{x_i-x_j}$$。
这个构造不难证明是符合要求的：
当 \(x=x_i\) 时，所有分子分母都相同，\(g_i(x)=1\)。
当 \(x=x_j(i\neq j)\) 时，一定存在一项分子为 \(0\) ，故\(g_i(x)=0\)。
那么 \(f(x)=\sum\limits_{i=1}^{n+1}y_ig_i(x)\)。
暴力带入计算的复杂度为 \(\Theta(n^2)\)。
P4781 【模板】拉格朗日插值
特殊情况
实践中经常有 \(x_i=i\) ，此时我们尝试化简一下上面的式子：
\[g_i(x)=\prod\limits_{j\neq i}\frac{x-j}{i-j}=\prod\limits_{j=1}^{i-1}\frac{x-j}{i-j}\prod\limits_{j=i+1}^{n+1}\frac{x-j}{i-j}=\frac{1}{(i-1)!}\prod\limits_{j=1}^{i-1}(x-j)\frac{(-1)^{n+1-i}}{(n+1-i)!}\prod\limits_{j=i+1}^{n+1}(x-j) \]\(O(n)\)，预处理 \((x-j)\) 的阶乘，阶乘逆元，前缀积和后缀积，就可以做到 \(\Theta(1)\) 查询 \(g_i(X)\)了。
总复杂度 \(\Theta(n)\)。
CF622F The Sum of the k-th Powers
可以证明自然数幂和是关于 \(n\) 的 \(k+1\) 次多项式，我们取 \(n+2\) 个位置 \(x=1,2,3,\dots n+2\)，计算出其函数值，之后应用上述拉插求出答案即可。
复杂度 \(\Theta(k)\)。
优化 DP
CF995F Cowmpany Cowmpensation
暴力 \(dp\) 是 \(O(nD)\) 的，要优化。
硬组合容斥应该也行，但是不够无脑。
因为本质不同的值只有 \(\Theta(n)\) 种，所以 \(dp\) 值是一个关于 \(D\) 的 \(n\) 次函数，那么带入 \(n+1\) 个 \(D\) 值求出 \(dp\)，然后插出来就行。
复杂度 \(\Theta(n^2)\)。
P4463 [集训队互测 2012] calc
思路差不多。
[省选联考 2022] 填树
考虑钦定最小值 \(l\)，算出所有值都在 \([l,l+K]\) 中的方案数，然后容斥减掉 \([l+1,l+K]\) 中的方案数。
考虑对于一个节点，对于不同的 \(l\) 产生的贡献是一个分 \(5\) 段的一次函数，那么把所有节点的段点拿出来总共就会把值域分成 \(O(n)\) 段，每段内所有节点都是一次函数，乘起来就是 \(n\) 次函数。
\(n\) 次函数的前缀和是 \(n+1\) 次函数，因此我们把每一段内拿出来做一个拉格朗日插值就可以了，第二问同理。
复杂度 \(\Theta(n^3)\)。
[NOI2019] 机器人
与上一题套路差不多，分段之后每段内拉插优化 \(dp\) 即可。
更进一步
如果我们不只满足于求 \(f(X)\)，而是想要求出 \(f_0,f_1\dots f_n\)，怎么办？
暴力是 \(O(n^3)\) 的。
考虑先 \(O(n^2)\)求出 \(F(x)=\prod\limits_{i=1}^n(x-x_i)\)，然后每次就是要查询 \(\frac{F(x)}{(x-x_i)}\)，短除法就行。
复杂度 \(O(n^2)\)。
这种东西经常可以优化一些卷积式。
对于多项式 \(F(x),G(x)\)，如果我们求出 \(f(i)=\sum\limits_jF_ji^j,g(i)=\sum\limits_jG_ji^j\)，那么 \((f\times g)(i)=f(i)g(i)\)，然后再插值还原出系数就行。
当然这样还是 \(O(n^2)\) 看起来没啥用。
但是如果我们要计算多项式 \(F_1\times F_2\dots \times F_m\)，每个多项式次数为 \(n\)，那么暴力卷积复杂度是 \(O(mn^2)\)，而该做法就可以做到 \(O(nm)\)。
CF1874E Jellyfish and Hack
暴力 \(dp\) 是 \(O(n^6)\) 的，瓶颈在于卷积，我们带入一些点值，然后把 \(dp\) 值看做多项式的系数，这样中间的所有卷积都转化为了点值的乘法，这样复杂度 \(\Theta(n^4)\)。
CF917D Stranger Trees
将树边的权值设为 \(x\)，非树边设为 \(1\)，那么矩阵树定理求出的答案多项式的 \(k\) 次项系数就是有恰好 \(k\) 条树边的方案数，
暴力维护多项式不可接受，因此带入点值运算，最后拉插还原。
复杂度 \(O(n^4)\)。