首页 > 代码库 > 【bzoj3209】 花神的数论题
【bzoj3209】 花神的数论题
http://www.lydsy.com/JudgeOnline/problem.php?id=3209 (题目链接)
题意
${sum(i)}$表示${i}$的二进制表示中${1}$的个数。求${\prod^n sum(i)}$
Solution
${f_{i,s}}$表示dp到第${i}$位，已经有${s}$个${1}$时的乘积。然后一路dfs就可以了。
细节
LL，返回值要与1取个max
代码
// bzoj3598#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf (1ll<<30)#define MOD 10000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL f[60][60],m;int n,t[60];LL dfs(int pos,LL s,int lim) { if (!pos) return s; if (!lim && f[pos][s]!=-1) return f[pos][s]; int end=lim ? t[pos] : 1; LL res=1; for (int i=0;i<=end;i++) (res*=max(1ll,dfs(pos-1,s+i,lim && i==end)))%=MOD; if (!lim) f[pos][s]=res; return res;}int main() { memset(f,-1,sizeof(f)); scanf("%lld",&m); for (n=0;m;m>>=1) t[++n]=m&1; printf("%lld",dfs(n,0,1)); return 0;}
【bzoj3209】 花神的数论题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。