解题思路:
深入理解lucas定理.
Lucas定理:把n写成p进制a[n]a[n-1]a[n-2]…a[0],把m写成p进制b[n]b[n-1]b[n-2]…b[0],则C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*….*C(a[0],b[0])模p同余。
这题p为2,所以a[i]和b[i]为0或者1。又因为C(1,0), C(1,1), 即当n等于1时,结果才等于1。
所以写出n的二进制,m从0遍历到n,每一次遍历把m写成二进制,如果要想结果为1,则必须在n的二进制串0对应的地方填上0(因为C(0, 0)=1),,其它地方可以填0或者1。
结论:把n化成二进制串,统计1的个数k,则结果为 2^k。#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <stack>#define LL long long using namespace std;int N;int main(){while(scanf("%d", &N)!=EOF){int cnt = 0;while(N){if(N & 1) cnt++;N >>= 1;}printf("%d\n", 1<<cnt);}return 0;}
梦想不分高低贵贱,只要你心中有梦,乐观充实地过好每一天。