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