[C++知识库]【二进制】【二项式定理】【组合数】C. Moamen and XOR

相同知识点的题目

https://blog.csdn.net/qq_50285142/article/details/122792736

前置知识

• 二项式系数之和：$C_n^0+C_n^1+C_n^2+C_n^3+...+C_n^{n?1}+C_n^n=2^n$
• 二项式奇数项系数之和等于偶数项系数之和，即
  $C_n^1+C_n^3+C_n^5+...=C_n^0+C_n^2+C_n^4+C_n^6+...=2^{n?1}$

题目链接

https://codeforces.com/problemset/problem/1557/C

长度为n的数组每个元素不超过$2^k$，问满足$a_1\&a_2\&a_3\&\dots \&a_n\ge a_1\oplus a_2\oplus a_3\oplus \dots \oplus a_n$的数组个数

对每一位二进制进行考虑，可以认为数组中的每个数共有k位二进制位

对数组中的数考虑形式如下图：（我认为应该在脑中形成模型）

我们考虑每一位的情况：

我们需要分奇偶进行考虑：考虑当前位相等和大于的情况（题目中是大于等于，分开考虑）

• n为奇数
  • 相等: 共$d_1=C_n^0+C_n^2+C_n^4+...+C_n^{n?1}+C_n^n=2^{n?1}+1$
    • 数组中的数该位全为1 :$C_n^n$
    • 数组中的数该位全为0:$C_n^0$
    • 该位有偶数个1,且存在0:$C_n^2+C_n^4+...+C_n^{n?1}$ (注意n为奇数)
  • 大于： 不存在
• n为偶数
  • 相等: 共$d_2=C_n^0+C_n^2+C_n^4+...+C_n^{n?2}=2^{n?1}?1$
    • 该位有偶数个1,且存在0:$C_n^2+C_n^4+...+C_n^{n?2}$
    • 数组中的数该位全为0:$C_n^0$
  • 大于:
    • 数组中的数该位全为1:$C_n^n=1$

接下来算结果：

• 首先相等的是一种情况，根据奇偶确定要使用的$d$，所有位都相等，答案为$d^k$
• 然后考虑大于的情况。d : 该位等于的情况 。 s：该位任意的情况，任意就是0和1两种情况，选择n次
  枚举第一个大于的二进制位置i，如果本位是大于，那么后面的k-i位就可以随意情况，前面的i-1个位必须为等于的情况。所以总的情况是$d^{i?1}+s^{k?i}$，需要枚举这个i（第一个大于的位置）

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod = 1e9 + 7;

ll ksm(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}	
	return res;
}
void solve()
{

	ll n, k;
	cin >> n >> k;
	
	ll res = 0;
	ll d = ksm(2, n - 1);
	ll s = ksm(2, n);
	d += (n & 1 ? 1 : -1);
	//ou shu: mei jv di yi ge da yu wei zhi
	if(n % 2 == 0)
		for(int i = 1; i <= k; i++)
			res = (res + ksm(s, k - i) * ksm(d, i - 1) % mod) % mod;
	res = (res + ksm(d, k)) % mod;
	
	cout << res << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
//	t = 1;
	while(t--) 
		solve();
	return 0;
}