BZOJ 3209花神の数論題(数位dp)

 
 
枚举的是二进制数 先预处理出所有i位二进制数中，含j个1的数的个数，就是C(i,j)
 
 
然后就是从高位到低位，处理填0还是1的情况 
 
 
填0：之后i-1位随机填0/1
 
 
填1：紧接着的[n对应的二进制数该位为0]的位只能填0(否则超过n) 
 
 
注意该算法计数到的所有情况不含SUM(n)！因此读入时，n++
 
  
 
数位dp是不是基本都要预处理 = = 
 
  
  
 
#include<stdio.h>
#include<stdlib.h>
#define MOD 10000007
typedef unsigned long long ULL;
ULL c[65][65]={0};
ULL ksm(ULL a,ULL n)
{
    ULL ans;
    a%=MOD;
    if(n==0) return 1;
    if(n==1) return a;
    ans=ksm(a,n/2);
    ans=(ans*ans)%MOD;
    if(n%2==1) ans=(ans*a)%MOD;
    return ans;
}
int main()
{
    ULL n,t,ans=1;
    int i,j,k=0,len=0;
    scanf("%llu",&n);
    n++;
    for(i=0;i<64;i++)//       
    {
        c[i][0]=1;
        for(j=1;j<i;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        c[i][i]=1;
    }
    for(t=n;t>0;t=t>>1)
        len++;
    for(i=len;i>=1;i--)
        if(n>>(i-1)&1)
        {
            for(j=0;j<i;j++)
                if(j+k!=0) ans=(ans*ksm(j+k,c[i-1][j]))%MOD;//     0(        1      1)
            k++;//     1(k:    k 1)
        }
    printf("%llu",ans);
    return 0;
}