hdu 4349 求C(n,0),C(n,1),C(n,2)...C(n,n).当中有多少个奇数 (Lucas定理推广)

Lucas定理:把n写成p进制a[n]a[n-1]a[n-2]...a[0],把m写成p进制b[n]b[n-1]b[n-2]...b[0],则C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余。

即:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)

这题是求C(n,0),C(n,1),C(n,2)...C(n,n).当中有多少个奇数
也是就是说 求C(n,m)%2==1 的个数 m的范围是0-n

C(n,m)%2,那么由lucas定理,我们可以写成二进制的形式观察

比如n=010 m为000 001 010
最终结果为 1+0+1=2
因为 C(0,1)=0
所以C(0,0)* C(1,0)*C(0,1)= 0
所以n = 010 中的0 不能对应m中的1 否则就会为了
n = 010 中的1 可以对应m中的0 或 1
也就变成了求n的二进制中有多少个1 求1的个数
最后结果为 2^(n中1的个数)

Sample Input
1 //n
2
11

Sample Output
2
2
8

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <string>
 6 # include <cmath>
 7 # include <queue>
 8 # include <list>
 9 # define LL long long
10 using namespace std ;
11
12
13 int main()
14 {
15     //freopen("in.txt","r",stdin) ;
16     int n ;
17     while(scanf("%d",&n)!=EOF)
18     {
19         int cnt=0;
20         while(n)
21         {
22             if(n&1)
23                cnt++;
24             n>>=1;
25         }
26         printf("%d\n",1<<cnt);
27     }
28     return 0;
29 }

时间: 09-20

hdu 4349 求C(n,0),C(n,1),C(n,2)...C(n,n).当中有多少个奇数 (Lucas定理推广)的相关文章

HDU 4349 Xiao Ming&#39;s Hope (Lucas)

题意:给定一个 n,问你在 C(n, 0) - C(n , n) 中有多少个奇数. 析:Lucas定理,C(b[i], a[i]),只要不为0,那么就是奇数,然后b[i],是固定的,也就是说a[i] 只有 b[i]+1种情况.最后乘起来就好. 代码如下: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <

HDU 4006 求第k大数 treap

裸题,瞬秒.. #include <stdio.h> #include <iostream> #include <algorithm> #include <math.h> #include <vector> #include <set> #include <map> #include <queue> using namespace std; #define L(id) tree[id].ch[0] #defin

HDU 4349 Xiao Ming&#39;s Hope 找规律

原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=4349 Xiao Ming's Hope Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1723    Accepted Submission(s): 1144 Problem Description Xiao Ming likes coun

HDU 4349 Xiao Ming&#39;s Hope(数学题,Lucas定理)

解题思路: 深入理解lucas定理. Lucas定理:把n写成p进制a[n]a[n-1]a[n-2]...a[0],把m写成p进制b[n]b[n-1]b[n-2]...b[0],则C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余. 这题p为2,所以a[i]和b[i]为0或者1.又因为C(1,0), C(1,1), 即当n等于1时,结果才等于1. 所以写出n的二进制,m从0遍历到n,每一次遍历把m写

HDU 4349 Xiao Ming&#39;s Hope

很无语的一个题. 反正我后来看题解完全不是一个道上的. 要用什么组合数学的lucas定理. 表示自己就推了前面几个数然后找找规律. C(n, m) 就是 组合n取m: (m!(n-m!)/n!) 如果n==11 : C(11,0):C(11,1):C(11,2):C(11,3):C(11,4):C(11,5): 分别为 (1/1); (1 / 11) ; (11*10 / 2*1)  ;   (11*10*9 / 3*2*1); (11*10*9*8 / 4*3*2*1) ;  (11*10*9

HDU 4349 组合数的奇数个数-杨辉三角&amp;Lucas定理

题意:给你一个n,求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])  modp同余 即:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) 来看这一题,求奇数,那么我们

HDU 3037 Saving Beans (Lucas定理)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3037 推出公式为C(n + m, m) % p, 用Lucas定理求大组合数取模的值 代码: #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int t; long long n, m, p; long long pow(long long n, long lo

组合数(Lucas定理) + 快速幂 --- HDU 5226 Tom and matrix

Tom and matrix Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=5226 Mean: 题意很简单,略. analyse: 直接可以用Lucas定理+快速幂水过的,但是我却作死的用了另一种方法. 方法一:Lucas定理+快速幂水过 方法二:首先问题可以转化为求(0,0),(n,m)这个子矩阵的所有数之和.画个图容易得到一个做法,对于n<=m,答案就是2^0+2^1+...+2^m=2^(m+1)-1,对于n>m

HDU 3037 Saving Beans (数论,Lucas定理)

题意:问用不超过 m 颗种子放到 n 棵树中,有多少种方法. 析:题意可以转化为 x1 + x2 + .. + xn = m,有多少种解,然后运用组合的知识就能得到答案就是 C(n+m, m). 然后就求这个值,直接求肯定不好求,所以我们可以运用Lucas定理,来分解这个组合数,也就是Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p). 然后再根据费马小定理就能做了. 代码如下: 第一种: #pragma comment(linker, "/STACK:10240