题目链接：https://www.luogu.com.cn/problem/P4317
与数字计数像极了，并且更容易一些，只是数据范围大一些，思路是完全一样的，并且前导0并没有影响：
找出二进制下有1个1的有多少数，2个1，3个1.....用&来拆分即可，最后用快速幂进行乘法运算进行一下优化。
AC代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const ll mod=10000007; ll dp[60][60][60]; int a[60]; ll ans[60]; ll ksm(ll x,ll y,ll p){ ll ans=1; while(y){ if(y&1) ans=ans*x%p; x=x*x%p; y>>=1; } return ans; } ll DFS(int pos,int limit,int now,int cnt){ if(pos==0) return now==cnt; if(!limit&&dp[pos][now][cnt]!=-1) return dp[pos][now][cnt]; int up=limit?a[pos]:1; ll ans=0; for(int i=0;i<=up;i++) ans+=DFS(pos-1,limit&&i==a[pos],now+i,cnt); if(!limit) dp[pos][now][cnt]=ans; return ans; } ll solve(ll x){ int len=0; ll sum=1; memset(dp,-1,sizeof(dp)); while(x){ a[++len]=x&1; x>>=1; } for(int i=1;i<=len;i++){ ans[i]=DFS(len,1,0,i); sum=sum*ksm(i,ans[i],mod)%mod; } return sum; } int main(){ ll n; scanf("%lld",&n); printf("%lld",solve(n)); return 0; }
原文：https://www.cnblogs.com/New-ljx/p/12451556.html
