题目描述
设$sum(i)$表示$i$的二进制表示中$1$的个数。
给出一个正整数$N$,花神要问你:$prod_{i=1}^nsum(i)$。
数据范围
对于$100$%的数据,$Nleq10^{15}$
考虑每一位二进制的拆解
#include <bits/stdc++.h> #define mod (ll)10000007 using namespace std; typedef long long ll; const int maxn=50+5; ll n,a[maxn],ans=1,cnt; ll qpow(ll a,ll b) { ll res=1,base=a; while(b) { if(b&1) res=res*base%mod; base=base*base%mod; b>>=1; } return res; } int main() { scanf("%lld",&n); for(int j=49;~j;j--) { for(int i=49;~i;i--) a[i]+=a[i-1]; if(n>>j&1) a[cnt++]++; } a[cnt]++; for(int i=1;i<=49;i++) ans=ans*qpow(i,a[i])%mod; printf("%lld ",ans); return 0; }
记忆化搜索:
$10^{15}$分解二进制位最多有五十位,可以枚举一共有多少位有1,50次
$dp[i][j][k]$表示在当前无限制条件下,已经枚举到了第$i$位,有了$j$个1,求有$k$个1的方案数。
结束条件$j=k$时才$return 1$。
#include <bits/stdc++.h> #define mod 10000007 using namespace std; typedef long long ll; int a[55]; ll n,dp[55][55][55],ans[55]; ll qpow(ll x,ll y) { ll res=1; while(y) { if(y&1) res=res*x%mod; x=x*x%mod; y>>=1; } return res; } ll dfs(int cnt,int flag,int now,int k) { if(now==k) return 1; if(!cnt) return now==k; if(!flag&&~dp[cnt][now][k]) return dp[cnt][now][k]; ll res=0; int Max=flag?a[cnt]:1; for(int i=0;i<=Max;i++) { res+=dfs(cnt-1,flag&&(i==Max),now+(i==1),k); } if(!flag) return dp[cnt][now][k]=res; return res; } ll query(ll x) { int cnt=0; ll res=1; while(x) { a[++cnt]=x&1; x>>=1; } for(int k=1;k<=50;k++) { for(int i=0;i<=a[cnt];i++) { ans[k]+=dfs(cnt-1,(i==a[cnt]),(i==1),k); } } for(int i=1;i<=50;i++) { res*=qpow(i,ans[i]); if(res>=mod) res%=mod; } return res; } int main() { memset(dp,-1,sizeof(dp)); scanf("%lld",&n); printf("%lld ",query(n)); return 0; }