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为奇数) 大于： 不存在 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 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