二进制数位dp，就是把原本的数字转化成二进制而以，原来是10进制，现在是二进制来做，没有想像的那么难
不知到自己怎么相出来的。。。感觉，如果没有一个明确的思路，就算做出来了，也并不能锻炼自己的能力，因为我现在需要训练的是做题的思维方法啊！
sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，求sum(1)—sum(N) 的乘积。
首先，这道题直接做，感觉无从下手，那么我就想，怎么来转换一下，求1~n中每个数的一的个数总相乘之积，首先感觉到，每个数都会有唯一对应的1的个数，且一的个数的取值只有最多60，因为n最大 10^15, 那么我就想，如果枚举1的个数k，计算有多少个数含有k个1，（因为数位dp就是来做，有多少满足的数，且不关注数的大小）这样就转化为数位dp的模型了
另外，发现含有k个1的数个数可能非常多，快速幂搞一搞啦，
不过快速幂要注意超long long 的情况！！，因为在很多题mod比较大，mod<根号2^31，平方之后就有可能超int！!!!!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long int ll;
const int MAXN=+;
const ll mod=; ll n,Ans;
ll c[MAXN][MAXN];
int l,wei[MAXN];
void pre()
{
for (int i=;i<=;++i)
c[i][]=;
for(int i=;i<=;i++)
for(int j=;j<=i;++j)
c[i][j]=c[i-][j-]+c[i-][j];//c[i][j]表示i位，j个1。
scanf("%lld",&n);
l=,n+=;//只能计算小于n的个数，所以要加1
while(n)
{
wei[++l]=n&;
n>>=;
}//将n转换为2进制。
}
ll Solve(int x)//解决有x个1的方案数
{
ll sum=;
for (int i=l;i>=;--i)
{
if(wei[i]==)
{
sum+=c[i-][x];
x--;
}
if(x<) break;
}
return sum;
}
ll Pow(ll a, ll b){
ll tot=;
a%=mod;
while(b)
{
if(b&)
{
tot=a*tot%mod;
tot%=mod;
}
b>>=;a*=a;a%=mod;
}
return tot;
}
int main()
{
pre();
Ans=1ll;
for(int i=;i<=l;++i)
Ans=Ans*Pow(i,Solve(i))%mod;
printf("%lld\n",Ans);
return ;
}