思想深奥,代码操简单的数学问题。
题目链接:http://poj.org/problem?id=3219
CSUST 2012年暑假8月组队后个人赛第12场:http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=11900#problem/D
D - Binomial Coefficients
Time Limit:1000MS Memory Limit:131072KB 64bit IO Format:%I64d
& %I64u
Description
The binomial coefficient C(n, k) has been extensively studied for its importance in combinatorics. Binomial coefficients can be recursively defined as follows:
C(n, 0) = C(n, n) = 1 for all n > 0;
C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for all 0 < k < n.
Given n and k, you are to determine the parity of C(n, k).
Output
For each test case, output one line containing either a “0
” or a “1
”, which is the remainder of C(n, k) divided by two.
题意:就是判断C(n,k)的奇偶性,如果为奇数就输出1否则输出0.
思路:按照杨辉三角找规律即可。C(n,k)(k<=n)的奇偶性取决于(n-k)与k的二进制表达式是否存在同一位上的两个数码均为1,若存在,则为偶数,反之为奇数。
证明: http://file.lw23.com/2/2a/2a6/2a623be7-8928-456d-82b5-d9818f808555.pdf
代码:
#include<stdio.h>
int n,k;//对于这个程序,定义全局变量比较快0ms过,否则要16ms
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
printf("%d\n",k&(n-k) ? 0 : 1);
}
return 0;
}