拉格朗日插值小应用

关于拉格朗日插值：我只会最简单的形式喵。

就是给 \(n\) 个点值，就能在 \(O(n^2)\) 的时间复杂度内求出当 \(x=a\) 的时候的值。

其标准形式是：\(\displaystyle \sum_{i=1}^n y_i \prod _{j\not =i}^n \frac{a-x_j}{x_i-x_j}\)

然后它更高深的应用我暂时不会喵。

但是也许能用在一些小清新 DP 式的优化。

主要在于如果发现式子有一个消不掉的巨大数字，并且能够确定整个结果是和它有关的多项式，就能先求出小值域下的结果，然后再插值回去。

CF995F Cowmpany Cowmpensation

题意：\(n\) 个点的树，给每个点分配权值 \([1,d]\)，父亲的权值必须大于儿子，求方案数。

\(f_{i,j}\) 表示整棵树的权值在 \(1\sim j\) 的方案数。

\(\displaystyle f_{p,i}=f_{p,i-1}+\prod_{v\in p} f_{v,i}\)

所有叶子的 \(f_{p,i}=i\)

感性理解一下，当在叶子上时，\(f_{p,i}\) 是一个关于 \(i\) 的一次函数，也就是多项式的项数为 \(2\) 。而考虑叶子们的父亲，就是把儿子们乘起来，变成了次数为叶子数加一的多项式。也就是说，到根的时候，最多是一个关于 \(i\)，项数为 \(n\) 次的多项式。这样可以 \(n^2\) 求出一部分点值，再拉格朗日插值把 \(d\) 带进去。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll ksm(ll x,ll y)
{
	ll ret=1;
	while(y)
	{
		if(y&1) ret=ret*x%mod;
		x=x*x%mod; y>>=1;
	}
	return ret;
}
int n,D;
const int maxn=6005;
int to[maxn],nxt[maxn],head[maxn],num;
void add(int x,int y){num++;to[num]=y;nxt[num]=head[x];head[x]=num;}
ll f[3002][3002],a[maxn],b[maxn];
void dfs(int p,int fa)
{
	for(int i=head[p];i;i=nxt[i])
	{
		if(to[i]==fa) continue;
		dfs(to[i],p); 
	}
	for(int j=1;j<=n;j++)
	{
		ll ret=1;
		for(int i=head[p];i;i=nxt[i])
			if(to[i]!=fa) ret=ret*f[to[i]][j]%mod;
		f[p][j]=(f[p][j-1]+ret)%mod;
	}
}
ll LA(int n,int D,ll *a,ll *b)
{
	ll ret=0;
	for(int i=0;i<=n;i++) 
	{
		ll x1=1,x2=1;
		for(int j=0;j<=n;j++)
		{
			if(i==j) continue;
			x1=x1*(D-a[j])%mod; x2=x2*(a[i]-a[j])%mod;
		}
		ret=(ret+x1*ksm(x2,mod-2)%mod*b[i]%mod)%mod;
	}
	return (ret%mod+mod)%mod;
}
int main()
{
	scanf("%d%d",&n,&D);
	for(int i=2;i<=n;i++)
	{
		int f; scanf("%d",&f);
		add(f,i);
	}
	dfs(1,0);
	for(int i=0;i<=n;i++) a[i]=i,b[i]=f[1][i];
	printf("%lld\n",LA(n,D,a,b));
}

[省选联考 2022] 填树

首先题面善良地告诉你被染色的点是一条链。

那么很容易写出第一问的转移方程。

枚举最小值为 \(L\)，当前情况下的答案为 \(A_{L}\)，设 \(f_{p}\) 表示以 \(p\) 为根，所有符合条件的链的数量，\(\displaystyle f_{i}=(b_i-a_i+1)\prod_{v \in son} f_v\)。

\(a_i,b_i\) 表示在整棵树上最小值为 \(L\) 的情况下，\(i\) 节点能到达的值域。\(a_i=\max\{l_i,L\},b_i=\min\{r_i,L+K-1\}\)，如果 \(a_i>b_i\) 则 \(f_i=0\)。

然后在每个点上合并儿子的时候算一下当前链和前面已经合并的 \(f_i\) 匹配一下，统计到总答案里。

那么 \(A_L=f_{1}-A_{L-1}\) 。这样减一下是因为 \(f_{i}\) 可能统计重复，就是没有最小值取到 \(L\) 的情况。

然后我们猜测 \(A_{L}\) 可能是关于 \(L\) 的，项数为 \(n+1\) 的多项式。因为可以发现最终答案就是两条链 \(b_i-a_i+1\) 乘到一起然后在 \(lca\) 处加起来的，而 \(b_i-a_i+1\) 是关于 \(L\) 的一次函数，假设 \(b_i-a_i+1=len_i\)，\(len_i\) 与 \(L\) 有如下关系：

\(len_i=\begin{cases}0 &\text{if } L+K-1<l_i&\text{or } L>r_i\\L+K-l_i &\text{if } L+K-1\geq l_i &\text{and } l_i \leq L\leq r_i\\ K &\text{if } L\geq l_i &\text{and } L+K-1 \leq r_i\\r_i-L+1 &\text{if }l_i\leq L\leq r_i&\text{and } L+K-1\geq r_i \end{cases}\)

上面就是为了向你展示 \(L\) 与每个点乘进去的权值的一次函数关系。

所以 \(A_L\) 是关于 \(L\) 的 \(n+1\) 项的多项式，不过每一项系数可能随 \(L\) 的大小改变。

但是如果我们把它想象成函数图像，就会明白能够使它发生转折的只有大约 \(O(n)\) 个点，剩下的时候都是连续的函数。那么我们就可以考虑拉格朗日插值：我们找到所有可能使函数转折横坐标，将它排序之后一段一段地考虑当前的函数。假如当前这段的函数图像覆盖的范围不太大（小于等于 \(n\)），那么我们完全可以把这段里所有的函数值全求出来加和；而如果覆盖的范围很大，我们求出这一段的前 \(n\) 个点值，然后做一个前缀和，再用结尾的横坐标做拉格朗日插值，得到的数字相当于这一段的和。对于每一段的函数都求出来所有的和，那么总的和就是答案啦。