hdu 4349 求C(n,0),C(n,1),C(n,2)...C(n,n).当中有多少个奇数 (Lucas定理推广)
2024-09-24 00:35:26
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
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# include <queue>
# include <list>
# define LL long long
using namespace std ; int main()
{
//freopen("in.txt","r",stdin) ;
int n ;
while(scanf("%d",&n)!=EOF)
{
int cnt=;
while(n)
{
if(n&)
cnt++;
n>>=;
}
printf("%d\n",<<cnt);
}
return ;
}
最新文章
- python中使用xlrd、xlwt操作excel表格详解
- 学习笔记-动态树Link-Cut-Tree
- SQL Server 阻止了对组件 &#39;Ad Hoc Distributed Queries&#39; 的 STATEMENT&#39;OpenRowset/OpenDatasource&#39; 的访问,因为此组件已作为此服务器安全配置的一部分而被关闭。系统管理员可以通过使用 sp_configure 启用 &#39;Ad Hoc Distributed Queries&#39;。有关启用 &#39;Ad Hoc Distributed Que
- 16)JAVA实现回调(Android,Swing中各类listener的实现)
- 爱维帮---LVS
- tar备份系统的方法
- SSD的来由与优势
- android UI跨线程操作
- vue.js2.0新手笔记(一)——安装
- redis单机安装以及简单redis集群搭建
- Spring Security 入门(1-7)Spring Security - Session管理
- 升讯威微信营销系统开发实践:微信接口的 .NET 封装
- Poj3176 Cow Bowling (动态规划 数字三角形)
- mysql数据库连接出问题,提示超时 java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.解决办法
- 将SD卡的音频设置为手机铃声后删除,手机铃声没有恢复到默认的问题
- extern的使用详解(多文件编程)——C语言
- linux中断源码分析 - 中断发生(三)
- 1100C	NN and the Optical Illusion
- javascript删除Cookie的正确方法(转载)
- Mybatis源码分析之SqlSession和Excutor(二)