BUPT2017 wintertraining(15) #8H

题意

求组合数C(n,i)，i从0到n，里面有几个奇数。

题解

直接打表的话可能就直接发现规律了。

规律是n的二进制里有几个1，答案就是2的几次方。

证明：

lucas定理有：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

然后取p为2。

所以展开后是C(0,0),C(0,1),C(1,0),C(1,1)的乘积。其中只有C(0,1)=0。

那么C(n,i)%2==1的条件就是n对应位为0，则i对应位必须是0，n对应位为1，则i对应位可以是1，也可以是0。

所以答案就是2的(1的个数)次方。

代码

#include <cstdio>

int main(){

	int n;

	while(~scanf("%d",&n)){

		int cnt=0;

		while(n){

			cnt+=(n&1);

			n>>=1;

		}

		printf("%lld\n", 1LL<<cnt);

	}

	return 0;

}

最新文章

1. opencv 小任务1 图片的缩放
2. Python之路 day1 用户登录多次被锁定
3. iOS 7新功能例子
4. 在sap系统设置纸张打印格式(针式打印机)
5. UVA 12730 Skyrk's Bar --期望问题
6. viewController的自动扩展属性导致TableViewGroupStyle时向上填充
7. Ruby on Rail学习笔记
8. 备忘====[HttpPost]和[AcceptVerbs(HttpVerbs.Post)]区别
9. Java条形码生成方案及二维码要点
10. pch文件出现no such file or directory错误
11. [Swust OJ 491]--分数的位置(简单版)
12. Google出品的自动Web安全扫描程序 Skipfish 下载及安装使用方法
13. Android L SDK -- 一些有趣的新功能
14. android 4G产品4G网络问题记录
15. ROC曲线的概念和意义
16. leetcode(js)算法10之正则表达式匹配
17. keepalived配置介绍
18. [UE4]Button
19. Atitti 过程导向 vs 结果导向 attlax的策
20. C++ sort函数用法 C中的qsort

热门文章

1. C. Polycarp Restores Permutation
2. siteServer创建网站中Mysql和SqlServer的区别
3. jmeter压测
4. composer 自动加载类 通过psr
5. [转帖]xserver相关知识汇总
6. 免费苹果账号（apple id）申请ios证书p12真机调试
7. python爬虫之Phantomjs安装和使用
8. python爬虫之Beautiful Soup的基本使用
9. Django--ORM和单表查询
10. python学习笔记（10）--组合数据类型(集合类型)