注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3157/3516/4126]国王奇遇记  

2015-06-06 20:45:58|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4126: 国王奇遇记

Time Limit: 15 Sec  Memory Limit: 128 MB
Submit: 367  Solved: 202
[Submit][Status][Discuss]

Description

Input

共一行包括两个正整数NM

Output

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

Sample Input

5 3

Sample Output

36363

HINT

1<=N<=10^9,1<=M<=200

Solution

http://trinkle.blog.uoj.ac/blog/478
网易不能打TeX真是蛋疼。。。
[BZOJ3157/3516/4126]国王奇遇记 - Trinkle - n+e
 
[BZOJ3157/3516/4126]国王奇遇记 - Trinkle - n+e
 
[BZOJ3157/3516/4126]国王奇遇记 - Trinkle - n+e
 
[BZOJ3157/3516/4126]国王奇遇记 - Trinkle - n+e
 
[BZOJ3157/3516/4126]国王奇遇记 - Trinkle - n+e
 
[BZOJ3157/3516/4126]国王奇遇记 - Trinkle - n+e
 

Code

Sol-1

/**************************************************************
    Problem: 3157
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:220 ms
    Memory:1232 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
#define p 1000000007
#define N 210
ll c[N][N],n,m,i,j,x,g[50][N],tot,mn,pn[N];
ll power(ll t,ll k){
    ll f=1;
    for(;k;k>>=1,t=t*t%p)if(k&1)f=f*t%p;
    return f;
}
void solve(int n,int tot){
    if(n==1){
        for(int i=0;i<=m;i++)g[tot][i]=m;
    }
    else if(n&1){
        solve(n-1,tot+1);
        for(int i=0;i<=m;i++){
            g[tot][i]=1;
            for(int k=0;k<=i;k++)g[tot][i]=(g[tot][i]+c[i][k]*g[tot+1][k])%p;
            g[tot][i]=g[tot][i]*m%p;
        }
    }
    else{
        solve(n>>=1,tot+1);mn=power(m,n);
        for(int i=1;i<=m;i++)pn[i]=pn[i-1]*n%p;
        for(int i=0;i<=m;i++){
            for(int k=0;k<=i;k++)g[tot][i]=(g[tot][i]+pn[i-k]*c[i][k]%p*g[tot+1][k])%p;
            g[tot][i]=(g[tot+1][i]+mn*g[tot][i])%p;
        }n<<=1;
    }
}
int main(){
    scanf("%lld%lld",&n,&m);pn[0]=1;
    if(m==1)return printf("%lld\n",(n*(n+1)/2)%p);
    for(c[0][0]=1,i=1;i<=m+1;i++)
    for(c[i][0]=1,j=1;j<=i;j++)
    c[i][j]=c[i-1][j]+c[i-1][j-1],c[i][j]>=p?c[i][j]-=p:1;
    solve(n,1);
    printf("%lld\n",g[1][m]);
}
Sol-2
/**************************************************************
    Problem: 3516
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:160 ms
    Memory:4796 kb
****************************************************************/
 
#include<cstdio>
#define N 1010
typedef long long ll;
int n,m,c[N][N],s[N],inv,mn,k,j;ll nk;
#define p 1000000007
int power(ll t,int k){
    ll f=1;
    for(;k;k>>=1,t=t*t%p)if(k&1)f=f*t%p;
    return f;
}
int main(){
    scanf("%d%d",&n,&m);
    if(m==1)return printf("%lld\n",(1LL*n*(n+1)/2)%p),0;
    mn=power(m,n+1),inv=power(m-1,p-2);
    s[0]=(1LL*(mn-1)*inv-1)%p;c[0][0]=1;
    for(nk=k=1;k<=m;k++){
        for(c[k][0]=j=1;j<=k;j++)c[k][j]=(c[k-1][j]+c[k-1][j-1])%p;
        for(j=0;j<k;j++)s[k]=(s[k]+1LL*c[k][j]*((k^j)&1?-1:1)*s[j])%p;
        nk=nk*n%p;s[k]=(nk*mn+s[k])%p*inv%p;
    }
    printf("%d\n",s[m]);
}
Sol-3
/**************************************************************
    Problem: 4126
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:10688 ms
    Memory:14480 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
#define N 500010
#define p 1000000007
int n,m,im,fac[N],i,j,inv[N],a[N],b[N],fa,fb,f0,pr[N],pt,pwm[N],vis[N],flag,tmp,ans;
int power(int t,int k){
    int f=1;
    for(;k;k>>=1,t=1LL*t*t%p)if(k&1)f=1LL*f*t%p;
    return f;
}
#define C(n,k) (1LL*fac[n]*inv[k]%p*inv[n-k]%p)
int main(){
    scanf("%d%d",&n,&m);n++;
    if(m==1)return printf("%lld\n",(1LL*n*(n-1)/2)%p),0;
    for(pwm[1]=inv[1]=1,i=2;i<=m+1;i++){
        if(!vis[i])pr[++pt]=i,pwm[i]=power(i,m),inv[i]=power(i,p-2);
        for(j=1;j<=pt&&1LL*i*pr[j]<=m+1;j++){
            vis[i*pr[j]]=1,
            pwm[i*pr[j]]=1LL*pwm[i]*pwm[pr[j]]%p,
            inv[i*pr[j]]=1LL*inv[i]*inv[pr[j]]%p;
            if(i%pr[j]==0)break;
        }
    }
    for(fac[0]=inv[0]=i=1;i<=m+1;i++)fac[i]=1LL*fac[i-1]*i%p,inv[i]=1LL*inv[i-1]*inv[i]%p;
    for(im=power(m,p-2),a[i=0]=1;i<=m;i++)a[i+1]=1LL*a[i]*im%p,b[i+1]=1LL*(pwm[i]+b[i])*im%p;
    for(flag=1,i=0;i<=m+1;i++,flag=-flag){
        tmp=C(m+1,i)*flag;if(tmp<0)tmp+=p;
        fa=(fa+1LL*tmp*a[i])%p,
        fb=(fb+1LL*tmp*b[i])%p;
    }
    f0=(p-1LL*fb*power(fa,p-2)%p)%p;
    if(n<=m){
        ans=(1LL*power(m,n)*(1LL*a[n]*f0%p+b[n])%p-f0+p)%p;
        printf("%d\n",ans);
    }
    else{
        for(flag=1,i=m;i>=0;i--,flag=-flag){
            tmp=(1LL*a[i]*f0+b[i])%p*inv[i]%p*inv[m-i]%p*power(n-i,p-2)%p;
            if(flag<0)tmp=p-tmp;ans=(ans+tmp)%p;
        }
        for(i=n-m;i<=n;i++)ans=1LL*ans*i%p;
        ans=(1LL*power(m,n)*ans%p-f0+p)%p;
        printf("%d\n",ans);
    }
}

  评论这张
 
阅读(878)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018