Question

ACM问题 数学方面的 这题有什么规律 求高手解答

http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1523
题目：
Description

Could you tell me the coefficient of x^k in (1+x)^n is odd or even?

Input

The first line of the input contains a integer T, indicate the number of test cases.
For each case, there are two integers n, k (0 <= k <= n <= 10^9).

Output

For each case, if the coefficient is odd, print "Odd" on a single line. Otherwise, print "Even" on a single line.

Sample Input

2
3 1
4 2

Sample Output

Odd
Even
楼下能再讲讲吗？？

Answer 1

http://baike.baidu.com/view/392493.htm
这个是牛顿二项式定理的内容。
楼上说的不错。
其实你可以直接转化为排列组合就行了：
3 1，表示3个人里选1个人，判断选人的方法数是奇数还是偶数。
4 2，表示4个人里选2个人，判断选人的方法数是奇数还是偶数。
C(3,1)=3,奇数。C(4,2)=6，偶数。
其实就是让你求C(n,k)%2是==1，还是==0？
由于k和n很大，你就要用下面这种公式：
(A/B)%K=(A%(B*K))/B;
(A*B)%K=((A%K)*(B%K))%K;

追问

如何编程 不是太懂

追答

告诉你一个规律吧，你先把这个数组都全部取2的模得到下面的：
1 1
1 0 1
1 1 1 1
1 0 0 0 1
...
其实你在第0行加一个1作为第1行，就可以构成一个不断递归的三角形。出现全部是1的行数为
1 2 4 8 16.......
每次出现一个全行为1的时候，把这行加上之前的所有行是一个三角形，共t行，它回在接下来t行并排出现2个这个三角形，且这2个三角形之间的空隙为一个全0的倒三角形。
我的ac代码如下：
#include
long long a[31];
void init(){
long long t=1;
for(int i=0;ia[x-1]){
cal(t,n-k+1);
}else
return 0;
}
}
int main()
{
int t;
long long n,k;
scanf("%d",&t);
init();
while(t--){
scanf("%I64d%I64d",&n,&k);
if(cal(n+1,k+1)){
printf("Odd\n");
}else
printf("Even\n");
}
return 0;
}

Answer 2

牛顿二项式定理可以递归实现，判断奇偶性直接除2取余