P4317 花神的数论题

题目背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。

题目描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的：设 \text{sum}(i)sum(i) 表示 ii 的二进制表示中 11 的个数。给出一个正整数 NN ，花神要问你 \prod_{i=1}^{N}\text{sum}(i)∏
i=1
N
​ sum(i) ，也就是 \text{sum}(1)\sim\text{sum}(N)sum(1)∼sum(N) 的乘积。

输入格式
一个正整数 N。

输出格式
一个数，答案模 10000007 的值。

输入输出样例
输入 #1复制
3
输出 #1复制
2
说明/提示
对于 100% 的数据，N≤10^15

简单的数位dp，我们考虑每个出现1出现的次数即可，然后就能计算答案了。

最后快速幂计算每个出现次数求积即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e7+7;
int n,a[60],cnt,dp[60][60][60],res[60];
int dfs(int pos,int s,int d,int limit){
	if(!pos)	return s==d;
	if(s>d)	return 0;
	if(!limit&&dp[pos][s][d]!=-1)	return dp[pos][s][d];
	int up=limit?a[pos]:1,ret=0;
	for(int i=0;i<=up;i++)	ret+=dfs(pos-1,s+(i==1),d,i==up&&limit);
	if(!limit)	dp[pos][s][d]=ret;
	return ret;
}
int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1)	res=res*a%p;	b>>=1;	a=a*a%p;
	}
	return res;
}
int solve(int x){
	while(n)	a[++cnt]=n&1,n>>=1;	int ans=1;
	for(int i=1;i<=50;i++){
		memset(dp,-1,sizeof dp);	res[i]=dfs(cnt,0,i,1);
	}
	for(int i=1;i<=50&&res[i];i++)	ans=ans*qmi(i,res[i])%p;
	return ans;
}
signed main(){
	cin>>n;
	cout<<solve(n)<<endl;
	return 0;
}