出于强迫症，想完成一下这个专题，其实就是我们工科生日常常用的插值方法，这里主要介绍一下它的原理与优势。
拉格朗日插值
参考blog：
拉格朗日插值（Lagrange Interpolation）是数值分析常用的插值方法，是对给定$n+1$个点坐标拟合出$n$次拉格朗日多项式，然后计算给定点值的数值计算方法
给出模板例题：P4781 【模板】拉格朗日插值
其实很容易想到，可以通过高斯消元解一个$n-1$元的线性方程组得出系数，然后计算结果，看到数据范围是$n\le2000$，高斯消元复杂度为$O(n^3)$，立即放弃，由此产生了拉格朗日插值
原理 & 公式
对$n$个点，可以构造出如下的$n-1$次多项式，从而计算出$f(k)$：
容易发现，内部的连乘式在$k=x_i$时取值为$1$，满足所有的点坐标，因此这个式子是符合题意的多项式，显然复杂度为：$O(n^2)$，可以开始搞了
代码
| inline ll Larange(){
ll ans=0;
for(int i=1;i<=n;i++){
ll tp=1;
for(int j=1;j<=n;j++){
if(i!=j){
tp=tp*(k-x[j])%mod*qpow(x[i]-x[j],mod-2,mod)%mod;
}
}
ans=(ans+y[i]*tp)%mod;
}
return (ans+mod)%mod;
}
|
在$x$取值连续时的优化
在$x$取值连续时，可以通过预处理前缀/后缀积和阶乘的方式优化方程，把复杂度降为$O(n)$
通常情况下，我们取$x$值为$[1,n]$共$n$个整数值，则上述多项式变为：
对于分子，$j\neq i$，因此需要维护分子的前缀积和后缀积如下：
对于分母，手推一下发现是两个阶乘相乘的形式，如下：
注意：上式中如果$n-i$为奇数则为负
那么整个式子就变为：
自然数幂次方和
例题：CF622F The Sum of the k-th Powers
题意十分简单，就是让计算 $\sum_{i=1}^ni^k \mod (10^9+7)$
数据范围：$1\le n\le 10^9, 0\le k\le 10^6$
题解
显然这题裸的$O(n\log k)$会T飞，需要考虑优化，根据数学知识，容易知道答案必然是一个$k+1$次多项式，那么联想到拉格朗日差值，我们只需要代入$k+2$个点，就可以拟合出这个多项式然后代入$n$求出答案，代入的点值可以连续，因此复杂度为$O(k)$
代码
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e6+5;
int n,k;
ll pre[maxn],suf[maxn],fac[maxn],f[maxn];
inline ll qpow(ll x,ll y,ll Mod){
ll res=1,base=x%Mod;
while(y){
if(y&1) res=(res*base)%Mod;
y>>=1;
base=(base*base)%Mod;
}
return res;
}
inline ll solve(){
ll ans=0;
pre[0]=suf[k+3]=fac[0]=1;
for(int i=1;i<=k+2;i++)
pre[i]=(pre[i-1]*(n-i))%mod;
for(int i=k+2;i>=1;i--)
suf[i]=(suf[i+1]*(n-i))%mod;
for(int i=1;i<=k+2;i++)
fac[i]=(fac[i-1]*i)%mod,
f[i]=(f[i-1]+qpow(i,k,mod))%mod;
for(int i=1;i<=k+2;i++){
ll tp=(f[i]*pre[i-1]%mod*suf[i+1]%mod*qpow(fac[i-1]*fac[k+2-i]%mod,mod-2,mod)%mod+mod)%mod;
if((k+2-i)&1) ans-=tp;
else ans+=tp;
ans=(ans+mod)%mod;
}
return ans;
}
int main(){
scanf("%d%d",&n,&k);
printf("%lld\n",solve());
return 0;
}
|