脚本宝典收集整理的这篇文章主要介绍了拉格朗日插值学习笔记，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
已知平面内的 (n) 个点可以唯一确定一个 (n-1) 次多项式。
给出这 (n(nle 2times 10^3)) 个点，请你求出这个多项式，对 (998244353) 取模。
正确性证明：可以发现，当 (exists i) 使 (x=x_i) 时，除了第 (i) 项，每一项的分子中都含有 (x-x_i) 这一项，因此其余项都被消去了；而第 (i) 项右边为 (y_icdot 1)，即 (y_i)。总而正确性得证。
该算法时间复杂度为 (O(n^2))。
下面介绍当 (x_i) 取值连续时的做法。
令 (pre_i=prod_{j=1}^i(x-j))，(suf_i=prod_{j=i}^n(x-j))
那么得到
时间复杂度为 (O(n))。
求 (K) 维空间内与原点的切比雪夫距离不超过 (N) 的所有整点到原点的切比雪夫距离之和，对 (10^9+7) 取模。
对于任意两点 (X=(x_1,x_2,ldots,x_K)) 与 (Y=(y_1,y_2,ldots,y_K))，定义它们的切比雪夫距离为 (max_{i=1}^K{vert x_i-y_ivert})。
数据范围：(Kle 10^6)，(Nle 10^9)。
设 (a_i) 为到原点距离为 (i) 个点数，答案为 (sum_{i=1}^N{a_itimes i})。
(a_i) 不方便统计，转化为到原点距离 (ge i land le N) 的点数，答案为 (sum_{i=1}^N{b_i})。
考虑容斥，总点数减去到原点距离 (<i) 的点数。
那么答案为 (n(2N+1)^K-sum_{i=1}^n(2i-1)^K)
((2i-1)^K) 是一个 (K) 次多项式，所以前缀和是一个 (K+1) 次多项式。
令 (f(x)=sum_{i=1}^x(2i-1)^K)，计算出 (f(1),f(2),ldots,f(K+2))，然后直接插值爆算即可。时间复杂度为 (O(Klog K))，足以通过。
有一个优化的小技巧，注意到 (g(x)=x^K) 为完全积性函数，可以线性筛得出，对于素数用快速幂算。
时间复杂度为 (O(n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000010,MLY=1000000007;
ll g[maxn],k,n,pre[maxn],suf[maxn],f[maxn],fac[maxn],ifac[maxn];
int pri[maxn],tot;
bool vis[maxn];
ll power(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a%MLY;
a=a*a%MLY;
b>>=1;
}
return ans;
}
int main(){
freopen("distance.in","r",stdin);
freopen("distance.out","w",stdout);
for(int i=2;i<maxn;++i){
if(!vis[i])pri[++tot]=i;
for(int j=1;i*pri[j]<maxn;++j){
vis[i*pri[j]]=1;
if(!(i%pri[j]))break;
}
}
fac[0]=ifac[0]=1;
for(int i=1;i<maxn;++i)fac[i]=fac[i-1]*i%MLY;
ifac[maxn-1]=power(fac[maxn-1],MLY-2);
for(int i=maxn-2;i;--i)ifac[i]=ifac[i+1]*(i+1)%MLY;
int T;scanf("%d",&T);
while(T--){
scanf("%lld%lld",&k,&n);
g[1]=1;
for(int i=1;i<=2*k+3;++i){
if(!vis[i])g[i]=power(i,k);
for(int j=1;i*pri[j]<=2*k+3;++j){
g[i*pri[j]]=g[i]*g[pri[j]]%MLY;
if(!(i%pri[j]))break;
}
}
for(int i=1;i<=k+2;++i)f[i]=(f[i-1]+g[2*i-1])%MLY;
pre[0]=suf[k+3]=1;
for(int i=1;i<=k+2;++i)pre[i]=pre[i-1]*(n-i)%MLY;
for(int i=k+2;i;--i)suf[i]=suf[i+1]*(n-i)%MLY;
ll ans=0;
for(int i=1;i<=k+2;++i)
ans+=f[i]*pre[i-1]%MLY*suf[i+1]%MLY*ifac[i-1]%MLY*ifac[k+2-i]%MLY*(((k+2-i)&1)?(MLY-1):1)%MLY;
printf("%lldn",(n*power(2*n+1,k)-ans%MLY+MLY)%MLY);
}
return 0;
}
有 (n) 个格子，现在用若干种颜色对这些格子的一部分染色（每种颜色可以用多次），染了 (k) 个格子就能够得到 (a_k) 的分数。
设 (b_i) 表示恰好用 (i) 种颜色进行染色的所有不同方案的分数和。
若两种方案染色的格子数不同，或将染色了的格子按照编号从小到大排列后有任意一对对应的格子颜色不同，就称这两种方案是不同的。
现在给出 (b_0,b_1,cdots,b_n) 在模 (998244353) 意义下的值，你需要求出 (a_0,a_1,cdots,a_n) 在模 (998244353) 意义下的值。
可以证明，答案是存在且唯一的。
数据范围：(nle 10^5)。
用 (c_i) 表示至多用 (i) 种颜色染色的不同方案的分数和。
枚举颜色个数，(c_i=sum_{j=0}^i{binom{i}{j}b_j})。
枚举涂的格子数，(c_i=sum_{j=0}^{n}{a_jcdot i^j})。
可以发现，(c_i) 就是 (A(x)=sum_{i=0}^n{a_jx^j}) 在 (x=i) 处的点值。
那么问题转化为求 (A(x)) 的系数。
可以 (mathtt{FFT}) 先求出 (c_i)。
考虑拉格朗日插值。
设 (d_i=frac{c_i}{prod_{jneq i}(i-j)})，(M=prod_{i=0}^n(x-i))。
可以用分治 (mathtt{FFT}) 求解。
时间复杂度为 (O(nlog^2 n))。
以上是脚本宝典为你收集整理的拉格朗日插值学习笔记全部内容，希望文章能够帮你解决拉格朗日插值学习笔记所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。