637
POJ 3219 二项式系数奇偶性的判定
这题想了很久 因为题里的给了递推公式 但是数据范围太大 用不了递归打表的 然后上网发现了
这个 其实还有N!/(K!(N-K)!)分别求出 N! K! (N-K)!中因子2的个数 如果N!中2的因子个数大于
后两项的和 那么就是偶数 如果等于就为奇数
判定准则Cn^m（m≤n）的奇偶性取决于m和n—m的二进制表达式中是否存在位于同一数位上的
两个数码都是1，如果存在，Cn^m是偶数，否则Cn^m就是奇数．
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
printf("%d\n", k&(n-k)?0:1);
return 0;
}
下面是我做的
N!/(K!(N-K)!)分别求出 N! K! (N-K)!中因子2的个数 如果N!中2的因子个数大于
后两项的和 那么就是偶数 如果等于就为奇数
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
int n,k;
long long a[35];
a[1]=2;
for(int i=2; i<=32; i++)
a[i]=2*a[i-1];
while(~scanf("%d%d",&n,&k))
{
if(n==k||k==0)
{
printf("1\n");
continue;
}
int w=0,b=0,c=0;
for(int i=1; i<=32; i++)
{
w+=n/a[i];
b+=k/a[i];
c+=(n-k)/a[i];
}
if(w>b+c)
printf("0\n");
else
printf("1\n");
}
return 0;
}
最后更新：2017-04-04 07:03:27