POJ 3219 Binomial Coefficients C++版

题目链接：http://poj.org/problem?id=3219

题意简单，求C(n，k)的奇偶性，

我的方法不简单，但分析简单，不过今天还看到个大神的分析，让我很是佩服

我门知道C(n，k)=n!/k!/(n-k)!那么就通过分析这三项的2的阶数来分析C(n，k)的2的阶数，也就是n!的阶数<=k!的阶数+(n-k)!阶数，则为奇数。

其中n!的2的阶数求解的方法为n/2+n/4+n/8….我就是用的这个方法，

1
2
3
4
5
6
7
8
9

int y(int d)
{
	int s=0;
	for(int i=2;d/i;i*=2)
		s+=d/i;
	return s;
}

1
2
3
4
5
6
7
8
9
10

int y(int d)
{
    int s=0;
    while((d=d>>1)!=0)
	s+=d;
    return s;
}

::cpp
/*Problem: 3219        User: awq123
**Memory: 244K        Time: 32MS
**Language: C++        Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int y(int d)
{
    int s=0;
    for(int i=2;d/i;i*=2)
        s+=d/i;
    return s;
}

int main()
{
    int n,k;
    while (cin>>n>>k)
    {
        if(k>n-k)
            k=n-k;
        if(y(n)<=y(n-k)+y(k))
            cout<<1<<endl;
        else
            cout<<0<<endl;
    }
}

这个题还见到了一种大神的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int n,k;
	while (cin>>n>>k)
	{
		if((k&n;)==k)
			cout<<1<<endl;
		else
			cout<<0<<endl;
	}
}