luoguP4317 花神的数论题 数位dp

这道题细节并不算太多，但是求方案数的时候一定不要乱取模！ 

如果非要取模的话也要遵循欧拉定理.  

code: 

#include <bits/stdc++.h>   
#define N 57  
#define ll long long  
#define mod 10000007
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
ll f[N][2][N];   
int num[N],cnt; 
int qpow(int x,ll y) 
{
    int tmp=1;  
    for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) tmp=(ll)tmp*x%mod;  
    return tmp;  
}
void init() 
{   
    f[1][0][0]=f[1][1][1]=1;       
    for(int i=2;i<=56;++i) 
    {
        for(int j=0;j<=i;++j)   
        { 
            f[i][0][j]+=f[i-1][0][j]+f[i-1][1][j]; 
            if(j) f[i][1][j]+=f[i-1][0][j-1]+f[i-1][1][j-1]; 
        }           
    }
}    
ll calc(ll x,int t) 
{
    memset(num,0,sizeof(num)),cnt=0; 
    while(x) 
    {
        num[++cnt]=x&1;  
        x>>=1;  
    }                                    
    // 先计算不满足 cnt 位的所有数字.     
    ll ans=0;    
    int cn=0;             
    for(int i=1;i<cnt;++i) ans+=f[i][1][t]; 
    for(int i=cnt;i>=1;--i) 
    {   
        if(num[i]&&i!=cnt&&cn<=t) ans+=f[i][0][t-cn];  
        cn+=num[i];    
    }
    return ans;   
}
int main() 
{ 
    // setIO("input");    
    ll n,ans=1;   
    init();  
    scanf("%lld",&n);            
    for(int i=2;i<=56;++i) 
    {   
        ans=ans*1ll*qpow(i,calc(n+1,i))%mod; 
    }  
    printf("%lld
",ans); 
    return 0; 
}