bzoj 3209 花神的数论题——二进制下的数位dp-白红宇

bzoj 3209 花神的数论题——二进制下的数位dp

阅读量：6679 次

发布时间：2019-06-25

本文共 2096 字，大约阅读时间需要 6 分钟。

题目：

可以枚举 “1的个数是...的数有多少个” ，然后就是用组合数算在多少位里选几个1。

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const int mod=1e7+7,N=70;//(1e7+7)%941==0ll n,dg[N];int jc[N],jcn[N],cnt,ans=1;int pw(int x,int k){    int ret=1;while(k){
    if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}int gcd(int a,int b){
    return b?gcd(b,a%b):a;}void exgcd(int a,int b,int &x,int &y){    if(!b){x=1;y=0;return;}    exgcd(b,a%b,y,x);y-=a/b*x;}void init(){    jc[0]=1;    for(int i=1;i<=62;i++)jc[i]=(ll)jc[i-1]*i%mod;    int y;exgcd(jc[62],mod,jcn[62],y);    for(int i=61;i>=0;i--)jcn[i]=(ll)jcn[i+1]*(i+1)%mod;}int C(int n,int m){    if(m>n)return 0;if(!m)return 1;    return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;}int main(){    init();    scanf("%lld",&n);    ll m=n;int p0=0;    while(m)    {        ll k=(m&-m);        for(;(1ll<
          
           =0&&k<=i;j--,k++)            ans=(ll)ans*pw(i,C(dg[j],i-k))%mod;//模数不是质数，不能对指数取模！！！     printf("%d\n",ans);    return 0;}

View Code

模数有毒吧怎么不是质数啊！这样都没法对指数取模了！

然后得知是数位dp。同样是枚举 “1的个数是...的数有多少个” ，但因为不是组合数，所以long long就行啦！

dp[ i ][ j ]表示第 i 位是0，后面从0..00到1..11中有多少个数有 j 个1。

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int N=62,mod=1e7+7;ll n,dp[N+5][N+5];int m,dg[N+5],cnt,ans=1;void init(){    dp[1][0]=1;    for(int i=2;i<=m;i++)        for(int j=0;j<=i;j++)            dp[i][j]+=dp[i-1][j]+dp[i-1][j-1];}int pw(int x,ll k){    if(!x)return 1;    int ret=1;while(k){
   if(k&1ll)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1ll;}return ret;}int main(){    scanf("%lld",&n);    for(m=0;m<=N&&(1ll<
         
          <=n;m++);    init();    ll c=n;int p0=0;    while(c)    {        ll k=(c&-c);        for(;(1ll<
          
           =0;i--,k++) { if(!i){ans=(ll)ans*k%mod;break;} for(int j=0;j<=dg[i]-1;j++) ans=(ll)ans*pw(j+k,dp[dg[i]][j])%mod; } printf("%d\n",ans); return 0;}