C. Moamen and XOR
莫阿门和伊扎特在玩游戏。他们创建了一个由n个非负整数组成的数组a其中每个元素都小于2k。
当a1&a2&a3&…&an≥a1⊕a2⊕a3⊕…其中&为按位与运算，⊕为按位异或运算。
请计算出Moamen数组a的中奖数量。
由于结果可能非常大，因此输出对1000000007取模的值(109+7)。
分析: 首先肯定要对 n n n 分奇偶,奇数个数字异或起来和偶数个数字异或起来情况肯定是不一样的,
当 n n n 为奇数
设 a 1 & a 2 & . . . a n a_1 \& a_2 \& ... a_n a1&a2&...an 为 x x x, a 1 ⊕ a 2 ⊕ a 3 ⊕ … a n a_1⊕a_2⊕a_3⊕…a_n a1⊕a2⊕a3⊕…an 为 y y y
x x x 最多有 k k k 位( 0 0 0 ~ k − 1 k-1 k−1)
当 x x x的第 i i i 位为 1 1 1, y y y的第 i i i 位一定为 1 1 1(因为奇数个 1 1 1 异或一定为 1 1 1)
当 x x x的第 i i i 位为 0 0 0, y y y 的第 i i i 位为 0 0 0
因为 x x x 的第 i i i位为 0 0 0, 所以一定有 0 0 0, 然后因为 y y y 的第 i i i 位必须要为 0 0 0, 所以 只能有偶数个 1 1 1
C n 0 + C n 2 + C n 4 . . . . + C n n − 1 C^0_n + C^2_n + C^4_n.... + C^{n-1}_n Cn0+Cn2+Cn4....+Cnn−1 = = = 2 n − 1 2^{n-1} 2n−1
所以为 2 n − 1 + 1 2^{n-1} + 1 2n−1+1, 这里为什么要 + 1 ? +1? +1?, 因为可能 x = 1 , y = 1 x = 1, y = 1 x=1,y=1 这种情况也要算上
然后求 2 n − 1 + 1 2^{n-1} + 1 2n−1+1 的 k k k 次幂就可以了, 因为有 k k k 位嘛
当 n n n 为偶数
1.当 x x x的第 i i i 位为 1 1 1, y y y的第 i i i 位一定为 0 0 0(因为偶数个 1 1 1 异或一定为 0 0 0)
所以后面随便填就可以了
2.当 x x x的第 i i i 位为 0 0 0, y y y 的第 i i i 位为 0 0 0(一定要有偶数个 0 0 0,且不为 0 0 0, 因为 & \& & 出来是 0 0 0 )
对于情况 1 1 1, a n s + = 2 ( k − i ) n ans += 2^{{(k-i)}^n} ans+=2(k−i)n
对于情况 2 2 2, a n s + = 2 n − 1 − 1 ans += 2^{n - 1} - 1 ans+=2n−1−1
#include<bits/stdc++.h>
#define x first
#define int long long
#define y second
#define gg exit(0);
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define db printf("debug\n");
const int N = 5e5 + 10, mod = 1e9 + 7;
using namespace std;
typedef pair<int,int>PII;
int T;
int n, k;int qmi(int a, int b)
{int res = 1;while(b){if(b&1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
void solve()
{ cin >> n >> k;if(n % 2 != 0){int sum = (qmi(2, n - 1) + 1 + mod) % mod;cout << qmi(sum , k) << '\n';}else {int sum = qmi((qmi(2, n - 1) - 1 + mod )% mod, k);for(int i = k - 1; i >= 0; i -- )sum = (sum + qmi((qmi(2, n - 1) - 1 + mod )% mod, k - i - 1) * qmi(qmi(2, i), n)) % mod;cout << sum << '\n';}
}
signed main()
{// io;// T = 1;cin >> T;while(T -- )solve();
}
