HDU 4349-Xiao Ming's Hope(Lucas定理的推广)-白红宇

HDU 4349-Xiao Ming's Hope(Lucas定理的推广)

阅读量：2029 次

发布时间：2019-04-28

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

题目地址：

题意：求C(n,0),C(n,1),C(n,2)…C(n,n).当中有多少个奇数(1<=n<=10^8)

思路：

在这里首先给出一个判断组合数奇偶性的一个规律：如果(n&m)==m，那么C(n,m)为奇数，否则为偶数

咱这里涉及的数值太大，所以并不能用。

其实本题是Lucas定理推导题，我们分析一下 C(n,m)%2,那么由lucas定理，我们可以写成二进制的形式观察，比如 n=1001101，m是从000000到1001101的枚举，我们知道在该定理中C(0,1)=0,因此如果n=1001101的0对应位置的m二进制位为1那么C(n,m) % 2==0,因此m对应n为0的位置只能填0，而1的位置填0，填1都是1（C(1,0)=C(1,1)=1)，不影响结果为奇数，并且保证不会出n的范围，因此所有的情况即是n中1位置对应m位置0，1的枚举，那么结果很明显就是：2^(n中1的个数)。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;using namespace std;const int Maxn=1e6+10;int main(){ int n; int cnt; while(~scanf("%d",&n)){ cnt=0; while(n>0){ if(n&1) cnt++; n>>=1; } printf("%d\n",1<

转载地址：http://hcsaf.baihongyu.com/

你可能感兴趣的文章