问题描述

[BZOJ5339](https://www.lydsy.com/JudgeOnline/problem.php?id=5339）

LG4593

题解

打出暴力之后，发现就是 \(F(x)=\sum\limits_{i=1}^{x}{i^{m+1}}\) 的时间复杂度比较高

暴力拉格朗日插值一下就好了

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxm=57;
const int mod=1000000007;

int T;
int n,m,x[maxm];

void Init(void){
    scanf("%lld",&T);
}

int fpow(int x,int p){
    int res(1);
    while(p){
        if(p&1) res=res*x%mod;p>>=1;
        x=x*x%mod;
    }
    return res;
}

int X[maxm],Y[maxm];

int doit(int x,int k){
    int res(0);
    for(int i=1;i<=x;i++) res=(res+fpow(i,k))%mod;
    return res;
}

void Preprocess(int k){
    for(int i=1;i<=k+2;i++) X[i]=i,Y[i]=doit(X[i],k);
}

int calc(int x,int k){
    int res(0);
    for(int i=1;i<=k+2;i++){
        int cnt(1);
        for(int j=1;j<=k+2;j++) if(i!=j) cnt=cnt*(X[i]+mod-X[j])%mod;
        cnt=fpow(cnt,mod-2);
        for(int j=1;j<=k+2;j++) if(i!=j) cnt=cnt*(x+mod-X[j])%mod;
        cnt=cnt*Y[i]%mod;
        res=(res+cnt)%mod;
    }
    return res;
}

void Solve(void){
    sort(x+1,x+m+1);
    Preprocess(m+1);
    int k=m+1,res(0);
    for(int i=1;i<=k;i++){
        res=(res+calc(n-x[i-1],k))%mod;
//      for(int j=1;j<=n-x[i-1];j++){
//          res=res+fpow(j,k);res=res%mod;
//      }
        for(int j=i;j<=m;j++){
            res=res-fpow(x[j]-x[i-1],k);
            res=res+mod;res%=mod;
        }
    }
    printf("%lld\n",res);
}

void Work(void){
    while(T--){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++) scanf("%lld",&x[i]);
        Solve();
    }
}

signed main(){
    Init();
    Work();
    return 0;
}