本文主要是介绍【二进制】【二项式定理】【组合数】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^0+C_n^1+C_n^2+C_n^3+...+C_n^{n-1}+C_n^n=2^n Cn0+Cn1+Cn2+Cn3+...+Cnn−1+Cnn=2n
- 二项式奇数项系数之和等于偶数项系数之和，即
C n 1 + C n 3 + C n 5 + . . . = C n 0 + C n 2 + C n 4 + C n 6 + . . . = 2 n − 1 C_n^1+C_n^3+C_n^5+...=C_n^0+C_n^2+C_n^4+C_n^6+...=2^{n-1} Cn1+Cn3+Cn5+...=Cn0+Cn2+Cn4+Cn6+...=2n−1
题目链接
https://codeforces.com/problemset/problem/1557/C
长度为n的数组每个元素不超过 2 k 2^k 2k，问满足 a 1 & a 2 & a 3 & … & a n ≥ a 1 ⊕ a 2 ⊕ a 3 ⊕ … ⊕ a n a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n a1&a2&a3&…&an≥a1⊕a2⊕a3⊕…⊕an的数组个数
对每一位二进制进行考虑，可以认为数组中的每个数共有k位二进制位
对数组中的数考虑形式如下图：（我认为应该在脑中形成模型）
我们考虑每一位的情况：
我们需要分奇偶进行考虑：考虑当前位相等和大于的情况（题目中是大于等于，分开考虑）
n为奇数- 相等: 共 d 1 = C n 0 + C n 2 + C n 4 + . . . + C n n − 1 + C n n = 2 n − 1 + 1 d_1=C_n^0+C_n^2+C_n^4+...+C_n^{n-1}+C_n^n=2^{n-1}+1 d1=Cn0+Cn2+Cn4+...+Cnn−1+Cnn=2n−1+1
- 数组中的数该位全为
1: C n n C_n^n Cnn - 数组中的数该位全为
0: C n 0 C_n^0 Cn0 - 该位有偶数个
1,且存在0: C n 2 + C n 4 + . . . + C n n − 1 C_n^2+C_n^4+...+C_n^{n-1} Cn2+Cn4+...+Cnn−1 (注意n为奇数)
- 数组中的数该位全为
- 大于： 不存在
- 相等: 共 d 1 = C n 0 + C n 2 + C n 4 + . . . + C n n − 1 + C n n = 2 n − 1 + 1 d_1=C_n^0+C_n^2+C_n^4+...+C_n^{n-1}+C_n^n=2^{n-1}+1 d1=Cn0+Cn2+Cn4+...+Cnn−1+Cnn=2n−1+1
n为偶数- 相等: 共 d 2 = C n 0 + C n 2 + C n 4 + . . . + C n n − 2 = 2 n − 1 − 1 d_2=C_n^0+C_n^2+C_n^4+...+C_n^{n-2}=2^{n-1}-1 d2=Cn0+Cn2+Cn4+...+Cnn−2=2n−1−1
- 该位有偶数个
1,且存在0: C n 2 + C n 4 + . . . + C n n − 2 C_n^2+C_n^4+...+C_n^{n-2} Cn2+Cn4+...+Cnn−2 - 数组中的数该位全为
0: C n 0 C_n^0 Cn0
- 该位有偶数个
- 大于:
- 数组中的数该位全为
1: C n n = 1 C_n^n=1 Cnn=1
- 数组中的数该位全为
- 相等: 共 d 2 = C n 0 + C n 2 + C n 4 + . . . + C n n − 2 = 2 n − 1 − 1 d_2=C_n^0+C_n^2+C_n^4+...+C_n^{n-2}=2^{n-1}-1 d2=Cn0+Cn2+Cn4+...+Cnn−2=2n−1−1
接下来算结果：
- 首先相等的是一种情况，根据奇偶确定要使用的 d d d，所有位都相等，答案为 d k d^k dk
- 然后考虑大于的情况。
d: 该位等于的情况 。s：该位任意的情况，任意就是0和1两种情况，选择n次
枚举第一个大于的二进制位置i，如果本位是大于，那么后面的k-i位就可以随意情况，前面的i-1个位必须为等于的情况。所以总的情况是 d i − 1 + s k − i d^{i-1}+s^{k-i} di−1+sk−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 zhiif(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;
}这篇关于【二进制】【二项式定理】【组合数】C. Moamen and XOR的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
