相关链接
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4349
神犇题解:http://blog.csdn.net/u013486414/article/details/48130553
题目大意
求${n \choose i},i \in [1,n]$中有多少个奇数
其中$n \le 10^{18}$
解题报告
原题相当于求${n \choose i} \% 2$有多少个为$1$
考虑使用$Lucas$定理,将模数设为$2$
此时相当于把$n,i$都转成了二进制下,然后单独考虑每一位
因为${1 \choose 1} = {1 \choose 0} = {0 \choose 0} = 1,{0 \choose 1} = 0$
所以当$n$的那个二进制位为$1$的时候,$i$那一位可以为$0/1$,但当$n$那一位为$0$时,$i$只能为$0$
所以最终方案数为$2^{\sum\limits_{i=0}^{63}{(n>>i) \& 1}}$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; int main() { for (LL n,ans;~scanf("%I64d",&n);){ ans = pow(2, __builtin_popcountll(n)) + 0.5; cout<<ans<<endl; } return 0; }