拉格朗日插值优化 $dp$

标签：拉格朗 Cowmpany 插值 多项式 优化 dp

拉格朗日插值优化 \(dp\)

目录

• 拉格朗日插值优化 \(dp\)
  • 拉格朗日插值
  • CF995F Cowmpany Cowmpensation
    • 重要结论
    • P4463 calc

拉格朗日插值

对于一个 \(n+1\) 次多项式 \(f(x)\)，若它经过 \(n\) 个点 \((x_1,y_1)\sim(x_n,y_n)\)

设其基本多项式：

\[\ell_i(x)=y_i\prod_{j=0,j\ne i}^n\dfrac{x-x_j}{x_i-x_j} \]

你会发现这个多项式经过 \((x_i,y_i)\) 和 \(\forall j\ne i\) \((x_j,0)\)，我们把所有这些加起来就会得到经过 \(n\) 个点的多项式 \(f(x)\)：

\[f(x)=\sum_{i=0}^n\ell_i(x) \]

for(int i=1;i<=n;++i){
	int s1=y[i],s2=1;
	for(int j=1;j<=n;++j){
		if(j==i) continue;
		s1=s1*(k-x[j])%mod;
		s2=s2*(x[i]-x[j])%mod;
	}
	ans+=s1*get_c(s2)%mod;
    ans=(ans+mod)%mod;
}

CF995F Cowmpany Cowmpensation

设 \(f_{x,i}\) 表示以 \(x\) 为根的子树用值域 \([1,i]\) 染色的方案数，则有：

\[f_{x,i}=f_{x,i-1}+\prod_{y\in son(x)} f_{y,i} \]

直接 \(dp\) 复杂度是 \(O(n\cdot d)\) 的

那么我们就需要一个重要的结论

重要结论

设 \(x\) 的子树大小为 \(sz_x\)，则 \(f_{x,i}\) 是关于 \(sz_x\) 的 \(n\) 次函数 (\(0\sim n-1\))

P4463 calc

标签：拉格朗,Cowmpany,插值,多项式,优化,dp
From： https://www.cnblogs.com/into-qwq/p/16729384.html