首页 > 代码库 > bzoj 3209: 花神的数论题 数位dp
bzoj 3209: 花神的数论题 数位dp
3209: 花神的数论题
Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。
Input
一个正整数 N。
Output
一个数，答案模 10000007 的值。
Sample Input
样例输入一
3
3
Sample Output
样例输出一
2
2
HINT
对于样例一，1*1*2=2；
数据范围与约定
对于 100% 的数据，N≤10^15
Source
原创 Memphis
思路：现在我们将问题转化成，找1-r区间内二进制数为i的个数，这样就是简单的数位dp了，然后求出个数之后，只需要快速幂一下即可；
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-4#define bug(x) cout<<"bug"<<x<<endl;const int N=1e5+10,M=1e6+10,inf=2147483647;const ll INF=1e18+10,mod=2147493647;ll f[60][60],bit[60];ll dp(int pos,int sum,int p,int flag){ if(pos==0)return (sum==p); if(flag&&f[pos][sum]!=-1)return f[pos][sum]; int x=flag?1:bit[pos]; ll ans=0; for(int i=0;i<=x;i++) { ans+=dp(pos-1,sum+i,p,flag||i<x); } if(flag)f[pos][sum]=ans; return ans;}ll getans(ll x,int p){ int len=0; while(x) { bit[++len]=x%2; x/=2; } return dp(len,0,p,0);}ll quick(ll a,ll b,ll c){ ll ans=1; while(b) { if(b&1)ans=(ans*a)%c; b>>=1; a=(a*a)%c; } return ans;}int main(){ ll r; scanf("%lld",&r); ll ans=1; for(int i=1;i<=60;i++) { memset(f,-1,sizeof(f)); //cout<<i<<" "<<getans(r,i)<<endl; //memset(f,-1,sizeof(f)); ans=(ans*quick(i,getans(r,i),10000007))%10000007; } printf("%lld\n",ans); return 0;}
bzoj 3209: 花神的数论题 数位dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。