[组合数学] Xiao Ming's Hope

题目链接

题目大意

求\(\sum_{i=0}^{n}(\complement^n_i \% 2)\)
换言之就是求\(\complement^n_1,\complement^n_2,...,\complement^n_n\)中奇数的个数
\(1 \leqslant n \leqslant 10^8\)
有多组测试数据

题解

由于n到了一亿的级别，暴力枚举肯定会超时。
于是我们考虑使用Lucas定理

Lucas 定理
将整数n分解为p进制数，每一位分别为\(p_1，p_2，...，p_k\)
将整数m也分解为p进制数，每一位分别为\(q_1，q_2，..., q_k\)
那么，\(\complement^n_m \equiv \prod_{i=1}^{k}\complement^{p_i}_{q_i}\)(MOD P)

因为我们只需要考虑每一个\(\complement^n_i\)是否为奇数，所以在本题中P=2，那么此时，我们只需要考虑对于每一个\(\complement^{p_i}_{q_i}\)，它为不为0就行了
我们知道\(\complement^1_1=1\)，\(\complement^1_0=1\)，\(\complement^0_1=0\)
那么很显然，对于n的一个二进制位，如果他为1，那么这一位就会有两种可能，反之就只有一种可能
于是我们只要求一下n的1的位数个数，记为cnt，则答案为\(2^{cnt}\)

代码

#include <cstdio>

int n, cnt;

int main() {
	while (scanf("%d", &n) != EOF) {
		cnt = 0;
		while (n > 0) {
			++ cnt;
			n &= n - 1;
		}
		printf("%lld\n", (1ll << cnt));
	}
	return 0;
} 

[组合数学] Xiao Ming's Hope

原文：https://www.cnblogs.com/luanmenglei/p/15096955.html