数论(Lucas定理) HDOJ 4349 Xiao Ming's Hope-白红宇

数论(Lucas定理) HDOJ 4349 Xiao Ming's Hope

阅读量：4634 次

发布时间：2019-06-09

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

题意：求C _(n,0),C _(n,1),C _(n,2)...C _{(n,n)中奇数的个数}

分析：Lucas 定理：A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) mod p同。即：Lucas (n,m,p)=C (n%p,m%p) * Lucas (n/p,m/p,p)

我是打表找规律的，就是: 2^二进制下1的个数。这定理可以求　　

收获：1. 没思路时一定要打个表找找规律 2. Lucas定理

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-27 8:48:05* File Name     :J.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int main(void) { int n; while (scanf ("%d", &n) == 1) { int cnt = 0; while (n) { if (n & 1) cnt++; n >>= 1; } ll ans = 1; for (int i=1; i<=cnt; ++i) ans *= 2; printf ("%I64d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4764360.html

你可能感兴趣的文章