洛谷 P4593 [TJOI2018]教科书般的亵渎

神仙伯努利数。。。网上一堆关于伯努利数的东西但是没有证明，所以只好记结论了？

题目本质要求\(\sum_{i=1}^{n}i^k\)

伯努利数，\(B_0=1,B_i=-\frac{\sum_{j=0}^{i-1}C_{n+1}^jB_j}{i+1}(i>0)\)

就这玩意（什么鬼）。。。

然后就神仙的有\(\sum_{i=1}^{n}i^k=\frac{\sum_{i=1}^{k+1}C_{k+1}^{i}B_{k+1-i}(n+1)^{i}}{k+1}\)了？

不会证啊QAQ

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 1000000007

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

il ll pow(ll x,ll y){

    ll ret=1;

    while(y){

        if(y&1)ret=ret*x%mod;

        x=x*x%mod;y>>=1;

    }

    return ret;

}

ll k,a[101],B[101],C[101][101],inv[101];

il ll query(ll x){

    ll ret=0;

    for(int i=1;i<=k+1;++i)ret+=C[k+1][i]*B[k+1-i]%mod*pow((x+1)%mod,i)%mod;

    return ret%mod*inv[k+1]%mod;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("4593.in","r",stdin);

    freopen("4593.out","w",stdout);

#endif

    ll T=gi(),n,m;

    C[0][0]=1;

    for(int i=1;i<101;++i){

        C[i][0]=1;

        for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

    }

    inv[1]=1;for(int i=2;i<101;++i)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;

    B[0]=1;

    for(int i=1;i<101;++i){

        B[i]=0;

        for(int j=0;j<i;++j)B[i]+=C[i+1][j]*B[j]%mod;

        B[i]=(mod-B[i]%mod*inv[i+1]%mod)%mod;

    }

    while(T--){

        n=gi(),m=gi();k=m+1;

        for(int i=1;i<=m;++i)a[i]=gi();

        std::sort(a+1,a+m+1);

        ll ans=0;

        a[++m]=n+1;

        for(int i=1;i<=m;++i){

            for(int j=i;j<=m;++j)ans+=(query(a[j]-1)-query(a[j-1])+mod)%mod;

            for(int j=m;j>=i;--j)a[j]-=a[i];

        }

        printf("%lld\n",ans%mod);

    }

    return 0;

}

巴特西

洛谷 P4593 [TJOI2018]教科书般的亵渎

洛谷 P4593 [TJOI2018]教科书般的亵渎

最新文章

热门文章