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;
}
全部评论

相关推荐

11-09 01:22
已编辑
东南大学 Java
高级特工穿山甲:羡慕,我秋招有家企业在茶馆组织线下面试,约我过去“喝茶详谈”😢结果我去了发现原来是人家喝茶我看着
点赞 评论 收藏
分享
10-28 11:04
已编辑
美团_后端实习生(实习员工)
一个2人:我说几个点吧,你的实习经历写的让人觉得毫无含金量,你没有挖掘你需求里的 亮点, 让人觉得你不仅打杂还摆烂。然后你的简历太长了🤣你这个实习经历看完,估计没几个人愿意接着看下去, sdk, 索引这种东西单拎出来说太顶真了兄弟,好好优化下简历吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务