欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

自然数k次幂的和 CF622 F .The Sum of the k-th Powers(拉格朗日插值)

程序员文章站 2022-06-07 09:52:29
...

自然数k次幂的和 CF622 F .The Sum of the k-th Powers(拉格朗日插值)
算是一个模板题,好多拉格朗日插值的题,最后化简之后的式子都用到了这个模板

代码:

//i的k次幂之和

typedef long long ll;
using namespace std;
const int MAXN=1e6+500;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
//::iterator it;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll n,k;
ll quick(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
}
ll inv(ll x){
    return quick(x,mod-2);
}
ll f[MAXN];
ll fac[MAXN];
ll iiik(ll n,ll k){
    for(ll i=1;i<=k+2;i++){
        f[i]=(f[i-1]+quick(i,k))%mod;
    }
    if(n<=k+2){
        return f[n];
        return 0;
    }
    ll p=1;
    for(ll i=1;i<=k+2;i++){
        p=(p*(n-i))%mod;
    }
    ll ans=0;
    for(ll i=1;i<=k+2;i++){
        ll m=1;
        // ll v1=inv(n-i)%mod;
        // ll v2=inv(fac[i-1]%mod*fac[k+2-i]%mod)%mod;
        if((k+2-i)%2==1)m=-1;
        m=((m*p%mod*f[i]%mod)*inv((n-i)*fac[i-1]%mod*fac[k+2-i]%mod))%mod;
        //ans=(ans+m*v1*v2%mod*f[i]%mod*p%mod)%mod;
        ans=(ans+m)%mod;
    }
    return (ans+mod)%mod;
}
ll ccc(ll n,ll m){
    if(n<m)return 0;
    return (fac[n] * quick(fac[m], mod - 2) % mod * quick(fac[n - m], mod - 2) % mod)%mod;
}
void init(){
    fac[0]=1;
    for(ll i=1;i<=1000050;i++)fac[i]=(fac[i-1]*i)%mod;
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    init();
    cin>>n>>k;  
    cout<<iiik(n,k)<<endl;
    return 0;
}

/*
4 2

30
*/

拉格朗日介绍
自然数k次幂的和 CF622 F .The Sum of the k-th Powers(拉格朗日插值)
参考:大佬的讲解