数论专题-白红宇

数论专题

阅读量：5918 次

发布时间：2019-06-19

本文共 1340 字，大约阅读时间需要 4 分钟。

占坑待补。

1、数位dp:

数位dp论文

http://wenku.baidu.com/link?url=967OXYqlrJC6X4kHfOIhIloao2vnoX3-V5X45w9q3plRy0D9ifraD_TzPIHj2BrAxrDIHj31bLzcAAnciWOHmvhMnxz3tCMI7v0PIdPDg27

ural 1057

给定区间，统计总和等于k个不相等的b的整数幂的个数。k和b范围1～20。

显然就是数位dp前i位有j个1,但是由于这是b进制，所以需要转换，把边界数字转化为不大于它的最大1组成的b进制。

然后就是借助二叉树这个工具进行思考，每次右转的时候把左子树加进来。

有一个想了很久才想通的问题d[i][j]其实本身不是一个二叉树，而是包含两个二叉树，一个根是0，一个根是1，

但是计算边界对应的答案的时候方便起见用0根。

计算二进制的时候>>1放在a[i]=tmp%b后面了导致二进制多了一位坑了1个半小时

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;#define ll long long#define LL long long#define inf 0x3f3f3f3f#define llinf 0x3f3f3f3f3f3f3f3f#define For(i,a,b) for(int i=a;i<=b;i++)#define ForD(i,a,b) for(int i=b;i>=a;i--)#define fp freopen("/Volumes/未命名2/Downloads/acm/in.txt","r",stdin)#define ptarr(a,x,y) for(int _=x;_<=y;_++) if(_!=y) cout<
                 
                  <<" ";else cout<
                  
                   <
                   
                    >x>>y>>k>>b;}void preprocess(){}int get(ll x,ll k){ ll tmp=x; int a[33],last=-1; For(i,0,31) { a[i]=tmp%b; if(a[i]>1) last=i; tmp/=b; } if(last!=-1){ For(t,0,last) a[t]=1; } x=0; ForD(i,0,31) { x<<=1; x|=a[i]; } int tot=0,ans=0; // ptarr(a,0,31); ForD(i,1,31) { if(x&(1<
                    
                     k) break; x=x^(1<