zcmimi's blog
avatar
zc
2020-08-23 10:18:00
  • 本文总阅读量
查看原题

点击跳转

细节: 如果从n开始有连续一段空白,那么这段空白要去掉

转换后可以发现只需要m+1张牌就可以

考虑每次"亵渎"的贡献

第一次"亵渎"的贡献就是\displaystyle \sum_{i=1}^n i^k剪掉空位的贡献

在空位p上使用"亵渎",有贡献的位置: [p+1,n],贡献为\displaystyle \sum_{i=1}^{n-p} i^k

减去空位多算的贡献即可

求自然数幂和可以考虑拉格朗日插值,递推法,伯努利数等

#include<bits/stdc++.h>
const int N=60,P=1000000007;
typedef long long ll;
int fac[N],ifac[N],pre[N],suf[N];
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return res;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=pw(fac[n],P-2);
    for(int i=n;i;--i)
        ifac[i-1]=1ll*ifac[i]*i%P;
}
void mod(int&x){if(x>=P)x-=P;}
int S(ll n,int k){
    pre[0]=1;
    for(int i=1;i<=k+2;++i)
        pre[i]=(n-i)%P*pre[i-1]%P;
    suf[k+3]=1;
    for(int i=k+2;~i;--i)
        suf[i]=(n-i)%P*suf[i+1]%P;
    int ans=0,y=0;
    for(int i=1;i<=k+2;++i){
        mod(y+=pw(i,k));
        int a=1ll*pre[i-1]*suf[i+1]%P*ifac[i-1]%P*ifac[k+2-i]%P;
        if((k-i)&1)a=P-a;
        mod(ans+=1ll*y*a%P);
    }
    return ans;
}
void solve(){
    static ll n,a[N];
    static int m,ans,k;
    std::unordered_map<ll,bool>v;
    scanf("%lld%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%lld",a+i),v[a[i]]=1;
    std::sort(a+1,a+m+1);
    while(v[n])--n,--m;
    k=m+1;
    ans=S(n,k);
    for(int i=1;i<=m;++i){
        mod(ans+=P-pw(a[i],k));
        mod(ans+=S(n-a[i],k));
        for(int j=i-1;j;--j)
            mod(ans+=P-pw(a[i]-a[j],k));
    }
    printf("%d\n",ans);
}
int main(){
    init(55);
    int T;scanf("%d",&T);
    while(T--)solve();
}
LG 4593 [TJOI2018]教科书般的亵渎
comment评论
Search
search