拉格朗日插值

· · 个人记录

基础理论

一般形式

可以通过如下方法构造出该多项式。 考虑构造 $n$ 个多项式，点值表示分别为： $$ A_0(x)=(x_0,y_0),(x_1,0),...,(x_n,0)\\ A_1(x)=(x_0,0),(x_1,y_1),...,(x_n,0)\\ ...\\ A_n(x)=(x_0,0),(x_1,0),...,(x_n,y_n) $$ 那么要构造的多项式 $f(x)=A_0(x)+A_1(x)+...+A_n(x)$。 考虑如何构造出多项式 $A_i(x)$，$\forall j\ne i$，我们希望 $A_i(x)=0$，考虑在其中加入形如 $\prod_{j\ne i}x-x_j$ 的项。并且希望 $A_i(x_i)=y_i$，因此当 $x=x_i$ 时考虑将 $\prod_{j\ne i}x-x_j$ 消成 $1$ 再乘上 $y_i$，即： $$ A_i(x)=y_i\prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j} $$ 那么： $$ f(x)=\sum_{i=0}^ny_i\prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j} $$ ### 点值连续时的线性插值 当点值为 $(1,y_1),(2,y_2),...,(n,y_n)$ 时对于 $\prod_{j\ne i}\dfrac{x-x_i}{x_i-x_j}$ 不难通过 $O(n)$ 预处理做到单次 $O(1)$ 查询。（注意分母 $-1$ 出现次数的奇偶性） ## 应用 ### 多项式前缀和 对于 $n$ 次多项式 $f(x)$，定义 $\Sigma f(x)=\sum_{i=0}^{x}f(i)$。有结论：$\Sigma f(x)$ 是 $n+1$ 次多项式。 > 例题：ABC208F Cumulative Sum > > 定义： > >$$ f(n,\ m)\ =\ \begin{cases}\ 0\ &\ (n\ =\ 0)\ \\ n^K\ &\ (n\ \gt\ 0,\ m\ =\ 0)\ \\ f(n-1,\ m)\ +\ f(n,\ m-1)\ &\ (n\ \gt\ 0,\ m\ \gt\ 0)\ \end{cases} >$$ > > 给定 $N,M,K$，计算 $f(N,M)$ 对 $10^9+7$ 取模的结果。 > > $0\le N\le 10^{18},0\le M\le 30,1\le K\le 2.5\times 10^6$。 固定 $m$。将 $f(n,m)$ 记作 $f_m(n)$。那么有： - $f_0(n)=n^{K}$。 - $\forall m > 0,f_m(n)=\sum_{i=0}^nf_{m-1}(i)$。 那么 $f_m$ 可以看成 $k+m$ 次多项式。$O(M(K+M))$ 递推出 $f_m(1)\sim f_{m}(m+k)$ 后线性插值即可。 ### 优化 DP 拉格朗日插值可以优化一类 dp，就是多项式类 dp，意思是每个状态存的实际上是一个多项式。 Q1：怎么知道是不是多项式类 dp？ A1：如果转移式当中只涉及到加减乘和乘方，多半是多项式 dp。 Q2：拉格朗日插值可以优化所有多项式 dp 吗？ A2：如果一次转移当中会使得多项式的次数剧增，那么优化了也是没有优化，所以要从实际出发。 （从 pengyule 的博客贺的） 一些分析多项式指数的基本方法： - 相乘次数相加。即 $\deg (f(x)\times g(x))=\deg f(x)+\deg g(x)$。 - 相加次数取最大。即 $\deg (f(x)+g(x))=\max(\deg f(x),\deg g(x))$。 - 加常数忽略。即 $\deg (f(x)+c)=\deg f(x)$。 - 复合次数相乘。即 $\deg (f(g(x)))=\deg f(x)\times \deg g(x)$。 - 前缀和次数+1。即 $\deg \Sigma f(x)=\deg f(x)+1$。 > 例题： P3643 [APIO2016] 划艇 > > 给定 $N$ 个区间 $[a_i,b_i]$，计算有多少个长度为 $N$ 的序列 $c$ 满足 $c_i\in [a_i,b_i]\cup \{0\}$，且若 $c_i>0$，则 $c_i>\max\limits_{1\le j<i}(c_j)$。 > > $1\le N\le 500,1\le a_i\le b_i\le 10^9$。 在 $[a_i,b_i]$ 范围内选数是一类经典的拉格朗日插值优化 DP 的模型。 令 $f_i(j)$ 表示考虑长度为 $i$ 的前缀选出来的最大值恰好为 $j$ 的方案数。 如果 $a_i\le j\le b_i$，那么： $$ f_i(j)=\sum_{0\le k\le j}f_{i-1}(j) $$ 否则： $$ f_i(j)=f_{i-1}(j) $$ 初始化 $f_0(0)=1$，$\forall j> 0$，$f_0(j)=0$。 这里的结论是 $f_i(j)$ 是分段函数，可以通过归纳证明。 把所有断点 $a_i,b_i+1$ 排序离散化后使用左闭右开的区间 $[arr_k,arr_{k+1})$ 表示分段。 对于当前第 $k$ 段的函数 $g_{i,k}$，令 $g_{i,k}(j)=\sum_{1\le t\le j} f_i(arr_k+t-1)$。 这里对多项式的维护只维护若干个点值。 从 $i-1$ 转移到 $i$ 时 $[a_i,b_i]$ 范围外的是不用动的。对于 $[a_i,b_i]$ 范围内的，多项式操作相当于加一个常数后前缀和再减去一个常数（消掉 $0$ 次项对多项式前缀和的影响）。那么从 $i-1$ 到 $i$ 多项式次数只会增加 $1$，而 $f_0$ 的次数为 $0$，因此维护 $n+1$ 个点值即可。 > 例题：CF995F Cowmpany Cowmpensation > > 树形结构，给每个节点分配工资（$[1, d]$），子节点不能超过父亲节点的工资，问有多少种分配方案。 > > $1\le n\le 3000,1\le d\le 10^9$。 令 $f_u(i)$ 表示考虑以 $u$ 为根的子树，$u$ 分配权值 $j$ 的方案数。将其看成多项式。 $$ f_u(i)=\prod_{v\in son(u)}\sum_{1\le j\le i}f_v(j) $$ 令 $g_u(i)=\sum\limits_{1\le j\le i}f_u(j)$。 那么： $$ f_u(i)=\prod_{v\in son(u)}g_v(i) $$ 即： $$ f_u=\prod_{v\in son(u)}g_v $$ 那么 $\deg f_u=\sum_{v\in son(u)}\deg g_v$。$\deg g_u=1+\deg f_u$。归纳可得 $\deg g_u=sz[u]$。 维护 $n+1$ 个点值，插值即可，复杂度 $O(n^2)$。