传送门

emmm，拉格朗日插值练手题，易发现\(k=m+1\)，然后我们发现一次亵渎的分数贡献是一段连续的幂和减去部分断点的幂和，大力插值就ok了。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我也就这种××题能在bzoj第一版了

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=60,mod=1e9+7;
int t,m;
ll a[N],f[N],pre[N],suf[N],fac[N],inv[N],n;
int qp(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
    return ret;
}
int calc(ll n){
    int k=m+2;
    fac[0]=suf[k+1]=1;pre[0]=n%mod;suf[k]=(n-k)%mod;
    for(int i=1;i<=k;i++)
        fac[i]=1LL*fac[i-1]*i%mod,pre[i]=1LL*pre[i-1]*((n-i)%mod)%mod;
    inv[k]=qp(fac[k],mod-2);
    for(int i=k-1;~i;i--)
        inv[i]=1LL*inv[i+1]*(i+1)%mod,suf[i]=suf[i+1]*((n-i)%mod)%mod;
    int res=0;
    for(int i=1;i<=k;i++)
        res=(res+((k-i)&1?-1LL:1LL)*pre[i-1]*suf[i+1]%mod*f[i]%mod*inv[i]%mod*inv[k-i]%mod)%mod;
    return res;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%d",&n,&m);int ans=0;
        for(int i=1;i<=m;i++)scanf("%lld",&a[i]);
        sort(a+1,a+m+1);
        for(int i=1;i<=m+2;i++)f[i]=(f[i-1]+qp(i,m+1))%mod;
        for(int i=0;i<=m;i++){
            ans=(ans+calc(n-a[i]))%mod;
            for(int j=i;j<=m;j++)ans=(ans-qp(a[j]-a[i],m+1)+mod)%mod;
        }
        printf("%d\n",ans);
    }
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄