bzoj 3209 花神的数论题（数位dp） - c++编程基础

TOP

bzoj 3209 花神的数论题（数位dp）

2015-11-21 01:04:33 来源: 作者: 【大中小】浏览:2次

3209: 花神的数论题

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 980 Solved: 460
[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

Sample Output

样例输出一

2

HINT

对于样例一，1*1*2=2；

数据范围与约定

对于 100% 的数据，N≤10^15

Source

原创 Memphis

思路：数位dp，对于二进制i这一位如果是1，那么后面有i-1位置可以填1或0，就可以知道新增加了多少个1，需要注意的是要记录这个数前面已经出现了几个1

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef long long ll; #define fre(i,a,b) for(i = a; i < b; i++) #define mem(t, v) memset ((t) , v, sizeof(t)) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define mod 10000007 #define INF 0x3f3f3f3f #define N 60 ll C[N][N]; //组合数 ll a[N]; ll n; ll len; void inint() { int i,j; C[0][0]=1; fre(i,1,N) { C[i][0]=1; fre(j,1,i) { C[i][j]=C[i-1][j]+C[i-1][j-1]; } C[i][i]=1; } } void solve() { int bit[N]; int len=0; while(n) { bit[++len]=n%2; n>>=1; } int now=0; int i,j; for(i=len;i>=1;i--) if(bit[i]) { for(j=0;j
            
             0) { if(y&1) ans=ans*x%mod; y>>=1; x=x*x%mod; } return ans; } int main() { inint(); int i; scanf("%lld",&n); mem(a,0); n++; solve(); ll ans=1; fre(i,1,N) ans=ans*pow_(i,a[i])%mod; pf("%lld\n",ans); return 0; }

记忆化代码：

//dp[i][j]代表第i位取j会得到的所有1的位数积

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef long long ll; #define fre(i,a,b) for(i = a; i < b; i++) #define mem(t, v) memset ((t) , v, sizeof(t)) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define mod 10000007 #define INF 0x3f3f3f3f #define N 60 ll dp[N][N]; int bit[N]; ll n; ll dfs(int pos,int n, bool bound) { if(pos==0) return n ? n:1; if(!bound&&dp[pos][n]!=-1) return dp[pos][n]; int up=bound? bit[pos]:1; ll ans=1; int i; fre(i,0,up+1) { if(i==0) ans*=dfs(pos-1,n,bound&&i==up); else ans*=dfs(pos-1,n+1,bound&&i==up); if(ans>=mod) ans%=mod; } if(!bound) dp[pos][n]=ans; return ans; } ll solve() { int i,len=0; while(n) { bit[++len]=n%2; n>>=1; } return dfs(len,0,true)%mod; } int main() { mem(dp,-1); scanf("%lld",&n); printf("%lld\n",solve()); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[Practical.Vim(2012.9)].Drew.Ne..	下一篇：BNUOJ33568 Glass Pyramid（DFS）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: