拉格朗日插值
首先一个定理：
n个点（横坐标不同）唯一确定一个最高n-1次的多项式。
拉格朗日插值法用于在 \(O(n^2)\) 的时间复杂度内解决以下问题
给定 \(n\) 个点 \((x_i, y_i)\) 求出这 \(n\) 个点唯一确定的最高 \(n - 1\) 次的多项式
拉格朗日插值表达式：
\[\tag{1} f(x) = \sum_{i = 1}^{n} y_i \prod_{j \neq i} \displaystyle \frac{x - x_j}{x_i - x_j} \]如果将题目给出的 \(n\) 个点 \(x\) 值代入 \((1)\) 式，刚好可以得到对应的 \(y\) 值，保证正确性
\(\text{预处理逆元}\) ，按照上式枚举即可得到多项式在 \(x\) 出的取值
横坐标式连续整数的拉格朗日插值
表达式变为
\[\tag{2} f(x) = \sum_{i = 1}^{n} y_i \prod_{j \neq i} \displaystyle \frac{x - j}{i - j} \]设 $ pre_i = \prod_{j = 1}^{i} (x - j), \ suf_i = \prod_{j = i + 1}^{n} (x - j) $
那么表达式变为
\[\tag{3} f(x) = \sum_{i = 1}^{n} y_i \displaystyle \frac{pre_{i - 1} \cdot suf_{i + 1}}{(i - 1)! \cdot (n - i)! \cdot (-1)^{n - i}} \]于是可以 \(O(n)\) 预处理阶乘逆元， \(O(n)\) 求值
重心拉格朗日插值法
如果每次加入一个数重新求多项式的插值，每次都是 \(O(n^2)\) ，不优
重心拉格朗日插值法可以在加入一个数后 \(O(n)\) 求出新的多项式的插值
\[f(x) = \sum_{i = 1}^{n} y_i \prod_{j \neq i} \displaystyle \frac{x - x_j}{x_i - x_j} \]\[f(x) = \sum_{i = 1}^{n} y_i \displaystyle \frac{\prod_{j = 1}^{n} x - x_j}{(x - x_i) \cdot \prod_{j \neq i} x_i - x_j} \]令 $ S = \prod_{j = 1}^{n} x - x_j, \ t_i = \prod_{j \neq i} x_i - x_j $
那么原式化为
\[\tag{4} f(x) = S \sum_{i = 1}^{n} \displaystyle \frac{t_i}{x - x_i} \]每次新加入一个点，更新 \(S\) 和前 \(n\) 个点的 \(t_i\) ，并计算出新的 \(t_{i + 1}\) ，然后按照 \((4)\) 式 \(O(n)\) 求和一遍即可得到新的多项式的插值
最常用最经典的套路应用
拉格朗日插值常用来求 \(\text{自然数幂和}\) ，即
\[f_k(n) = \sum_{i = 1}^{n} i^k \]通过一系列证明可以得知 \(f_k\) 是一个 \(k + 1\) 次多项式（其实是我不会证）
那么我们就可以求出前 \(n + 2\) 个点 \(f_k\) 值，然后应用拉格朗日插值公式求解
因为我们取的是连续的前 \(n + 2\) 个点，所以得到每个点的 \(f_k\) 值后可以 \(O(k)\) 插值
如果求前 \(n + 2\) 个点的 \(f_k\) 值使用快速幂，复杂度为 \(O(k \log k)\) ，如果使用线性筛，在质数处快速幂，复杂度为 \(O(k)\)
例题：
数学题题解：
考虑 \(dp\) ，设 \(f_{i, j}\) 表示前 \(i\) 门课程，B神碾压了 \(j\) 个人的方案数，设 \(g_i\) 表示第 \(i\) 门课程的分数方案数
\[f_{i, j} = \sum_{k = j}^{n - 1} f_{i - 1, k} \binom{k}{k - j} \binom{n - 1 - k}{r_i - 1 - (k - j)} \times g_i \]意思是，原来有 \(k\) 个人被B神碾压，新的一门课程有 \(k - j\) 个人不再被碾压，剩下多余的比B神高的名次 \(r_i - 1 - (k - j)\) 由本来就不被B神碾压的人 \(n - 1 - k\) 瓜分，不能给被B神碾压的人（不符合题意）最后乘上分数方案数
\[g_i = \sum_{j = 1}^{u_i} j^{n - r_i} \ (u_i - j)^{r_i - 1} \]枚举B神的分数，按照排名两边的人随便选
根据自然数幂和的结论，\(g(x)\) 是一个次数不超过 \(n + 1\) 次的多项式，可以使用拉格朗日插值法求值
前面说过 $ f_k(x) = \sum_{i = 1}^{x} i^k $ 是 \(k + 1\) 次多项式
即，它可以表示为 $ f_k(x) = \sum_{i = 1}^{x} a_i x^i $
前面都是求多项式在某点处的值，拉格朗日插值法也可以求出多项式的系数
\[\tag{1} f(x) = \sum_{i = 1}^{n} y_i \prod_{j \neq i} \displaystyle \frac{x - x_j}{x_i - x_j} \]这里面 \(x_i, x_j, y_i\) 都是常数， \(x - x_j\) 是一次多项式，直接用多项式乘法和多项式加法是 \(O(n^3)\) ，如果预处理出 $\prod_{j = 1}^{n} x - x_j $ 多项式，每次需要的时候除以一个 \(x - x_i\) ，可以做到 \(O(n^2)\)
具体的，设 \(g(x) = f(x) \times (x + c)\) (\(c\) 为常数)
那么 $ g_i = f_{i - 1} + f_i \times c , \ f_{i - 1} = g_i - f_i \times c$
例题：BZOJ 3601 一个人的数论（没有链接）
简单题意：给定 \(n\) 的质数拆分形式，给定 \(d\) ，求
\[\sum_{i = 1}^{n} [\gcd(i, n) = 1] i^d \ (mod \ 10^9 + 7) \]\[\sum_{i = 1}^{n} \sum_{j \mid i , \ j \mid n} \mu(j) \ i^d \]\[\sum_{j \mid n} \mu(j) \ j^d \sum_{i = 1}^{\left \lfloor \textstyle \frac{n}{j} \right \rfloor} i^d \]按照开头说过的 $ f_k(x) = \sum_{i = 1}^{x} a_i x^i $ 将 $ \sum_{i = 1}^{\left \lfloor \frac{n}{j} \right \rfloor} i^d $ 转化
\[\sum_{j \mid n} \mu(j) \ j^d \sum_{i = 1}^{d + 1} a_i \ (\lfloor \textstyle \frac{n}{j} \rfloor)^i \]\[\tag{5} \sum_{i = 1}^{d + 1} a_i \sum_{j \mid n} \mu(j) \ j^d \ (\lfloor \textstyle \frac{n}{j} \rfloor)^i \]设 $ f(n) = \sum_{j \mid n} \mu(j) \ j^d \ (\lfloor \textstyle \frac{n}{j} \rfloor)^i $
前面的系数 \(a_i\) 用拉格朗日插值法求得， \(f(n)\) 是一个积性函数，考虑按照质因子分别求解
$ f(p^c) = \sum_{j = 0}^{c} \mu(p^j) \ (pj)d \ (p^{c - j})^i $
当 \(j \ge 2\) 时 \(\mu(p^j)\) 为 \(0\)
所以
\[f(p^c) = \sum_{j = 0}^{c} \mu(p^j) \ (p^j)^d \ (p^{c - j})^i \]\[f(p^c) = \mu(1) \ 1^d \ (p^c)^d + \mu(p) \ p^d \ (p^{c - 1})^i \]\[f(p^c) = p^{cd} - p^{ci - i + d} \]至此，\((5)\) 式解决
大多数题不会像个板子题问，需要我们自己判断多项式的次数，再应用拉格朗日插值法
例题：BZOJ 3453 tyvj 1858 XLkxc（没有链接）
简单题意：给定 \(k, a, n, d \ 。 k \le 123\) , \(a, n, d\) 在\(int\)范围内，求
\[\sum_{i = 0}^{n} \sum_{j = 1}^{a + d \times i} \sum_{x = 1}^{j} x^k \]设
\[h(x) = \sum_{x = 1}^{j} x^k \]\[g(n) = \sum_{j = 1}^{n} \sum_{x = 1}^{j} x^k \]\[f(n) = \sum_{i = 0}^{n} \sum_{j = 1}^{a + d \times i} \sum_{x = 1}^{j} x^k \]根据自然数幂和的结论，\(h(x)\) 为次数为 \((k + 1)\) 的多项式，\(g(x)\) 为次数为 \((k + 2)\) 的多项式，\(f(x)\) 为次数为 \((k + 3)\) 的多项式 （一个求和号次数加1）
预处理出 \(g\) 在前 \(k + 3\) 个点处的值，应用 \(k + 4\) 次插值求出 \(f\) 在前 \(k + 5\) 个点处的值（记得也要算0），最后应用一次插值求出 \(f\) 在 \(n\) 处的值
考虑 \(dp\) ，设 \(f_{i, j}\) 表示前 \(i\) 个位置的数从 \([1, j]\) 中选，所有序列的值的和
我们考虑序列有序（单调递增）的情况，最后答案乘以 \(n!\) 即可
\[\tag{1} f_{i, j} = f_{i - 1, j - 1} \times j + f_{i, j - 1} \]考虑第 \(j\) 个数字选不选，转移
我们假设 \(f_{n, j}\) 是 \(j\) 的 \(g(n)\) 次多项式
\[\tag{2} f_{i, k} - f_{i, j - 1} = f_{i - 1, j - 1} \times j \]左边是 \(g(i) - 1\) 次的多项式（是一个差分形式）
右边是 \(g(i - 1) + 1\) 次多项式（乘以了一个系数）
所以 $ g(n) - 1 = g(n - 1) + 1 $
又知道 \(g(0) = 0\) ，所以 \(g(n) = 2n\)
\(f_{n, j}\) 是 \(j\) 的 \(2n\) 次多项式
直接暴力 \(DP\) 出 \(f(n, 1)\) 到 \(f(n, 2n + 1)\) 然后应用拉格朗日插值法求出 \(f(n, k)\)
标签：拉格朗,frac,插值,多项式,sum,笔记,prod From： https://www.cnblogs.com/wenqizhi/p/17069376.html