POJ3252 round number 组合数学 - c++编程基础

由于省赛的粗心以及无法互相检查队友之间的小错误，导致致命伤，所以接下来做到的好题目，代码中都自己仔细标好，做好小习惯

在做数位DP分类下的题目，这道题目一开始怎么想都觉得用数位DP肯定超时，最后想了很久一点思路都没有，后来看了一下题解，发现都是有排列组合做的，没办法只好用组合数学做了，看了一下别人的思路，发现不是特别难，对于基础要求比较高，所以这道题目觉得是一个好题，解析什么的发现了一篇写的很好的博客，不如就转那位大神的解析算了，感觉他写的解析很仔细，而且有图片结合，比较易懂，而且还详细声明了组合公式的一些性质，我的方法跟他有一些区别，但是解题思路没什么区别所以无伤大雅

http://blog.csdn.net/zhengnanlee/article/details/9794625

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                  > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // //vector
                    
                     G[30012]; // int num[300 + 5];//存二进制数 int cnt; int round_num[300 + 5];//存round number 个数 void clear() { memset(num,0,sizeof(num)); memset(round_num,0,sizeof(round_num)); } LL C(LL m, LL n) { if(m > n - m) m = n - m; LL ans = 1,pos = m; while(pos --) { ans *= n--; while(ans % m == 0 && m > 1) ans /= m--; } return ans; }//求组合数 void init() { round_num[1] = 0; for(int i=2;i<35;i++) {//长度为i,最高位为1 round_num[i] = 0; for(int j=1;j<=i - j;j++)//二进制中有j个1,1的个数要小于0 round_num[i] += C(j - 1, i - 1); } }//预处理存round_number个数的数组 void cal_bin(int n) { cnt = 0; while(n) { num[cnt++] = n%2; n /= 2; } }//二进制处理 int cal(int n) { cal_bin( n ); int ans = 0; int num0 = 0,num1 = 1; for(int i=0;i
                     
                      =0;i--) { if(num[i] > 0) { for(int j=0;j<=i && num1 + j <= cnt - num1 - j;j++) ans += C(j,i); num1++;//1的个数 } else num0++;//0的个数 } return ans; } int main() { int n,m; clear(); init(); int cccc; while(scanf("%d %d",&n,&m) == 2) { printf("%d\n",cal(m + 1) - cal(n)); } return 0; }