背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。
背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。
一个正整数 N。
一个数，答案模 10000007 的值。
对于样例一，1*1*2=2；
数据范围与约定
对于 100% 的数据，N≤10^15
数位DP+数论
令f[x]表示sum[i]=x的i的个数，则最终答案等于(1^f[1])*(2^f[2])*(3^f[3])*……
因为底数的范围很小，而10000007=941*10627，所以底数和10000007一定互质，根据欧拉定理，只要将指数对phi(10000007)=9988440取模就可以了。
那现在问题就是如何求f[x]。
从高位向低位进行数位DP，具体方法见程序。
为什么各种各样的DP自己都想不出来...(╯‵□′)╯︵┻━┻
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define mod 10000007
#define phi 9988440
using namespace std;
ll n,ans=1,c[60][60],f[60];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch>='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void dp(ll x)
{
int tmp=0,cnt=0;ll now=0;
while ((1ll<<tmp)<x) tmp++;
D(i,tmp,0) if (now+(1ll<<i)<=x)
{
F(j,0,i) (f[j+cnt]+=c[i][j])%=phi;
cnt++;now+=(1ll<<i);
}
}
inline ll getpow(ll x,ll y)
{
ll ret=1;
for(;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
return ret;
}
int main()
{
scanf("%lld",&n);
F(i,0,50)
{
c[i][0]=1;
F(j,1,i) c[i][j]=(c[i-1][j-1]+c[i-1][j])%phi;
}
dp(n+1);
F(i,1,50) ans=ans*getpow(i,f[i])%mod;
printf("%lld\n",ans);
}
原文：http://blog.csdn.net/aarongzk/article/details/51440613