bzoj3157 3516 国王奇遇记

Description

Input

共一行包括两个正整数N和M。

Output

共一行为所求表达式的值对10^9+7取模的值。

特判m=1

m≠1时：

设S[u]=sigma(i^u*m^i)

m*S[u]=sigma(i^u*m^(i+1))

=sigma((i-1)^u*m^i)+n^u*m^(n+1)

两式相减得(m-1)*S[u]=n^u*m^(n+1)-sigma((i^u-(i-1)^u)*m^i)

S[u]=(n^u*m^(n+1)-sigma((i^u-(i-1)^u)*m^i))/(m-1)

i^u-(i-1)^u可以展开，从而由S[0..u-1]计算出S[u]，预处理二项式系数（组合数）即可

边界条件S[0]=sigma(m^i)=(m^n-1)*m/(m-1)

除法要取逆元

时间复杂度为O(m²logn)

#include<cstdio>

typedef long long lint;

const int P=;

lint f[][];

lint s[];

bool d[];

int n,m;

lint power(lint x,lint t){

    lint v=,c=x;

    while(t){

        if(t&)v=v*c%P;

        c=c*c%P;

        t>>=;

    }

    return v;

}

lint div(lint a,lint b){

    return a*power(b,P-)%P;

}

lint S(int m1){

    if(d[m1])return s[m1];

    lint v=power(n,m1)*power(m,n+)%P;

    for(int i=m1-,j=-;i>=;i--,j=-j){

        lint r=S(i)*f[m1+][i+]*j;

        v+=r;

        v%=P;

    }

    v=div(v,m-);

    d[m1]=;

    return s[m1]=v;

}

int main(){

    scanf("%d%d",&n,&m);

    if(m==){

        printf("%lld",n*1ll*(n+)/%P);

        return ;

    }

    f[][]=;

    d[]=;

    s[]=div(power(m,n)-,m-)*m%P;

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

        for(int j=;j<=i;j++)f[i][j]=(f[i-][j]+f[i-][j-])%P;

    }

    printf("%lld\n",(S(m)+P)%P);

    return ;

}

巴特西

bzoj3157 3516 国王奇遇记

Description

Input

Output

最新文章

热门文章