题目大意：令Sum(i)为i在二进制下1的个数 求∏(1<=i<=n)Sum(i)
一道很简单的数位DP 首先我们打表打出组合数 然后利用数位DP统计出二进制下1的个数为x的数的数量 最后输出∏(1<=x<=logn)x^ans[x]即可
此题的坑在于这题的组合数和数位DP的结果都是指数 对指数取模不能直接取 要取Phi(p)
于是我们对10000006取模 然后这题就WA了 因为10000007不是个质数！
10000007=941*10627 于是我们得到Phi(p)=940*10626=9988440 对这个数取模即可
其实不取模就可以，一定不会爆long long的。。。我是何必呢这是。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 10000007
#define Phi_M 9988440
using namespace std;
typedef long long ll;
ll n,f[60][60],ans[60],output=1;
void Digital_DP(ll x)
{
int i,j,cnt=0;
ll now=0;
for(i=1;1ll<<i<=x;i++);
for(;~i;i--)
if(now+(1ll<<i)<=x)
{
for(j=0;j<=i;j++)
ans[j+cnt]=(ans[j+cnt]+f[i][j])%Phi_M;
++cnt;
now+=(1ll<<i);
}
}
ll Quick_Power(ll x,ll y)
{
ll re=1;
while(y)
{
if(y&1)re*=x,re%=M;
x*=x,x%=M;
y>>=1;
}
return re;
}
int main()
{
int i,j;
for(i=0;i<=55;i++)
{
f[i][0]=1;
for(j=1;j<=i;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1])%Phi_M;
}
cin>>n;
Digital_DP(n+1);
for(i=1;i<=55;i++)
output*=Quick_Power(i,ans[i]),output%=M;
cout<<output<<endl;
}