之前教练在提高班讲这个玩意......
学 FFT 之前来巩固一下。
模板
如果给出 \(n\) 个点 $(x_i,y_i) $则可以唯一确定一个 \(n-1\) 次多项式 \(f\)。其值为：
特殊地，当 \(x_i=i\) 的时候，其值为：
容易发现此时可以在 \(O(n)\) 或 \(O(n\log n)\) 的时间内计算出一个 \(f\)，瓶颈在如何求逆元（毕竟通常在模意义下做）。
为了方便记忆下文的重心插值法，我们定义拉格朗日多项式 \(l_i(x)=\prod_{i\neq j}\frac{x-x_j}{x_i-x_j}\)，那么常规插值公式就是 \(f(x)=\sum_{i=1}^{n}y_i\times l_i(x)\)。
我们发现当我们新增一个点的时候，常规的拉格朗日插值，需要重新 \(O(n^2)\) 地计算一遍。此时，我们可以利用重心拉格朗日插值法来改进。
定义重心权 \(w_i=\frac{y_i}{\prod_{i\neq j}x_i-x_j}\)，设 \(l(x)=\prod (x-x_i)\)，那么原来的插值公式可以改写成：
即
如果能预先知道 \(w_i\) 的值，那么单次带入计算就是 \(O(n)\) 的。而加入一个点的时候，更新所有 \(w_i\) 的复杂度显然也是线性的（先暂不考虑求逆元问题）。
所以我们发现在对同一个多项式，多次求点值；或者每次加入一个点然后求一个点值，这两种情况，重心拉格朗日插值法都可以单次线性地解决。
注意到在存在 \(x_i\) 使得 \(x\equiv x_i(\bmod 0)\) 的时候分母为 \(0\) 是不存在逆元的，所以谨慎使用重心插值法。
经典应用：求 \(\sum_{i=1}^{n}i^k\)。
我们知道 \(k=1\) 的时候，\(f(n)=\sum_{i=1}^{n}\) 有 \(2\) 次的公式，而 \(k=2\) 时也有 \(3\) 次的公式。事实上 \(f(n)\) 是 \(k+1\) 次多项式。这实际上是两个结论的体现：
-
若数列 \(a\) 是一个 \(k\) 阶多项式，则其差分数列 \(d\) 是 \(k-1\) 阶多项式。
-
若数列 \(a\) 是一个 \(k\) 阶多项式，则其前缀和数列 \(s\) 是 \(k+1\) 阶多项式。
这是两个非常重要的结论。
回到刚才的问题，我们要求前 \(n\) 个正整数的 \(k\) 次方和，它实际上是 \(k+1\) 次的一个多项式。那么我们可以任选 \(k+2\) 个正整数 \(x_i\) 算出 \(f(x_i)\)，显然我们会取 \(1\sim (k+2)\)。这样可以 \(O(k)\) 的确定 \(k+2\) 个点值。又因为 \(x_i=i\)，所以可以在 \(O(k)(O(k\log k))\) 的时间内求解。
模板：CF622F
1.ABC208F Cumulative Sum
当时这场打过，被这题虐了。
实际上就是求数列 \(i^k\) 的 \(m\) 阶前缀和数列的第 \(n\) 项的值。由于原数列是 \(k\) 次的 （\(f(x)=x^k\)），所以 \(m\) 阶前缀和数列是 \(m+k\) 次的。那么我们只要计算 \(m+k+1\) 个点即可。
然后我没想到正解是 \(O(m\times (m+k+1))\) 直接暴力算点值就可以了...... 算出来以后直接插值即可。
另外这题中其实存在一个有用的结论：考虑一个数列 \(a_1,a_2,...,a_n\) 的 \(m\ge 1\) 阶前缀和 \(s_1,s_2,...,s_n\)。显然 \(s_n\) 是 \(a_1,a_2,...,a_n\) 的一个权为正整数的线性组合。事实上 \(s_n=\sum_{i=1}^{n}\dbinom{n-i+m-1}{m-1}\times a_i\)。用插板法易证。
这个结论出现在了 ARC137D Prefix XORs 中，你注意到这里的系数组合数实际上是一个形如 \(\dbinom{a+b}{b}\) 的形式，在ARC137D中你还需要探讨这样的组合数什么时候是奇数。当然这和拉插已经无关了。
2.ARC118F Growth Rate
感觉知道是拉插以后再做就很简单了......
首先想到这样一个 \(dp\)：\(dp(i,j)\) 是 \(X_i=j\) 时，\(X_i\sim X_{n+1}\) 有多少种可能。那么 \(\sum_{i=1}^{m}dp(1,m)\) 就是所求的。
转移也是很简单的：\(dp(i,j)=\sum_{k\in [a_i\times j,m]}dp(i+1,k)\)。初始化 \(dp(n+1,i)=[1\le i\le m]\)。朴素转移是 \(O(nm^2)\) 的，注意到可以前缀和优化成 \(O(nm)\)，然而还是远远不够。观察到我们可以接受大概在 \(O(n^2)\) 级别的东西。如果经验丰富的话应该就有尝试拉插的意识了......
而 \(dp(n+1)\) 是一个 \(0\) 次的函数，它的前缀和就是 \(1\) 次的。而每一个 \(dp(n)\) 都是 \(dp(n+1)\) 的两个前缀和相减，所以 \(dp(n)\) 是 \(1\) 次的...... 到最后不难推出 \(dp(1)\) 是 \(n\) 次的。而我们要求的是 \(dp(1)\) 的前缀和的第 \(m\) 项，这是 \(n+1\) 次的。
但是这还是没解决转移的问题，虽然我们只关注 \(f(1,1\sim n+2)\) 但是这些状态也要用到 \(f(2,m)\) 这样第二维很大的状态......
自然地，我们想对每轮的 \(dp\) 维护它的前缀和序列，在下一次的计算中去用。但我们其实不需要存下这个序列..... 因为我们知道了前缀和序列的次数是 \(O(n)\) 级别的，所以维护 \(O(n)\) 级别个点，用点值的形式来维护多项式，这样求前缀和某项值的时候可以用拉插 \(O(n)\) 计算（因为维护的点值的 \(x\) 坐标连续）。所以对于我们关心的 \(O(n^2)\) 个状态，我们都可以 \(O(n)\) 计算，时间复杂度从 \(O(nm)\) 降到了 \(O(n^3)\)。
但是直接做，这个会跑得飞快。这是为啥捏，哦，原来 \(a_i=1\) 的时候我们算的第 \(a_i\times j-1\) 项前缀和是 \(\le n\) 的，这玩意在上次存储的点值里已经有了，其实是 \(O(1)\) 的，而 \(a_i\ge 1\) 的情况显然最多出现 $\log $ 次，否则就不存在答案了。所以理性分析后发现是 \(O(n^2\log m)\) 的......
另外注意，其实那个 \(dp_{n+1}\) 不能说是完全的 \(0\) 次的，实际上是一个分段函数，在一个界内是 \(0\) 次的。事实上每个 \(dp_i\) 都只是在一个界 \([1,R_i]\) 内有值，在界外都是 \(0\)。
这个界 \(R\) 是好算的：\(R_{n+1}=m,R_{i}=\left\lfloor\frac{R_{i+1}}{a_i}\right\rfloor\)。