首页 > 代码库 > hdu 4349 Xiao Ming's Hope (Lucas定理推导)
hdu 4349 Xiao Ming's Hope (Lucas定理推导)
题意:求C (n,0),C (n,1),C (n,2)...C (n,n).奇数的个数
思路:我们分析C(n,m)%2,那么由Lucas定理可知,n和m可以写成二进制的形式,假设n=1001101,那么m是0~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<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> using namespace std; int main() { int n; while(cin>>n) { int num=0; while(n) { if(n&1) { num++; } n=n/2; } int ans=1; for(int i=0;i<num;i++) ans=ans*2; cout<<ans<<endl; } return 0; }
hdu 4349 Xiao Ming's Hope (Lucas定理推导)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。