题目大意：
花神的题目是这样的 设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你 派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。
要对10000007（非质数）取模
n<=10^15
分析：
O(nlogn)暴力显然可以想出来。显然会tle
这是从1~n一个一个枚举并变成二进制算的，但是我们是否可以向普通的数位dp，一次性枚举许多个数呢？
二进制的n，大概最多50位。例如21=10101.它显然可以拆成二进制下的10000+100+1
那么，我们是否可以尝试着去先算出来1~10..0的sum乘积？
假设这是一个n位数，也就是有n-1个零
考虑只有一个1的数字个数，C(n,1)，即，在n个位置上，取1个位置变成1的方案数。那么，sum[i]=1的数的贡献就是1^c(n,1)
只有二个1，C(n-1,2)，注意，是n-1位，因为除了特殊的10..000之外，其他的数都只有n-1个位置可放1。同理，sum[i]=2的数的贡献就是2^c(n-1,2),因为本身就是连乘嘛，交换律结合律就先把不同个数的数所做的贡献乘起来。
三个1同理。
……
以21=10101为例，这样我们可以切掉n的第一个10000以下的方案。
现在我们要处理10001~10100的方案数，我们仍然可以利用刚才处理100的思路，
只是，放一个1在最后的三位，必然每次都要加上之前已经有过的那一个1（10000），所以，是2^c(3,1)
2个1同理，是3^c(2,2)
这样，就解决问题了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=;
ll ans=;
ll sum;
ll wei;
ll c[][];
ll n;
ll qm(ll x,ll y)
{
ll ret=,base=x;
while(y)
{
if(y&) ret=(ret*base)%mod;
base=(base*base)%mod;
y>>=;
}
return ret;
}
int main()
{
c[][]=;
for(int i=;i<=;i++)
{
c[i][]=;
for(int j=;j<=;j++)
c[i][j]=c[i-][j-]+c[i-][j];
}//直接打表就好，
//注意，组合数将作为指数部分，不能取模 C(50,25)long long也开的下，
scanf("%lld",&n);
wei=;sum=;//sum，已经处理出来的之前的1的个数
for(wei=;wei>=;wei--)//按位枚举
{
if(n&((ll)<<wei-))
{
ans=(ans*qm(sum+,wei))%mod;//处理1个的特殊情况
for(int k=sum+,s=;k<=sum+wei-;k++,s++)
{
ans=(ans*qm(k,c[wei-][s]))%mod;
}
sum++;
}
}
printf("%lld",ans);
return ;
}
总结：
数位dp的最初思想的来源，就是利用整千，整万，整十万的整齐特殊性质，可以利用可以想到的数学方法，对枚举进行大幅的简化，直接减少到O(logn)
这个题其实算是数位dp的裸题，还是比较常规的。
对于其他的符合规定的第k小的数（启示录），是先预处理整位的情况，再按位枚举，考虑每个数能填几，从而类似康拓展开，找到第k小的数。
或者[l,r]区间内多少个满足限制的数，前缀和思想，求l-1以内，再求r以内做差就好。