Problem Link 737Div2 C
This is my solution. First, represent the $$$n$$$ numbers in binary. Each number has $$$k$$$ digits, where each digit can be $$$0$$$ or $$$1.$$$ Let $$$a_{i, j}$$$ represent the $$$j$$$th digit (from left to right) of $$$a_i$$$, where $$$a_i$$$ is represented in binary.
Now,
$$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$$$is true if for all $$$1 \le j \le k,$$$
$$$a_{1,j} \,\&\, a_{2,j} \,\&\, a_{3,j} \,\&\, \ldots \,\&\, a_{n,j} \ge a_{1,j} \oplus a_{2,j} \oplus a_{3,j} \oplus \ldots \oplus a_{n,j}.$$$Let's consider the inequality for $$$j = 1,$$$ because others values of $$$j$$$ are similar.
$$$a_{1,1} \,\&\, a_{2,1} \,\&\, a_{3,1} \,\&\, \ldots \,\&\, a_{n,1} \ge a_{1,1} \oplus a_{2,1} \oplus a_{3,1} \oplus \ldots \oplus a_{n,1}.$$$If more than one of $$$a_{i,1} = 0$$$ for $$$1 \le i \le n,$$$ then the left side of the above inequality is going to be zero. This requires the right side of the above inequality to be zero, so an even number of $$$a_{i,1}$$$ should be $$$1$$$.
Also, if all of $$$a_{i,1}=1,$$$ then that is another possible case. This only needs to be considered if $$$n$$$ is odd.
Now, using the above two paragraphs, there are
$$$\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots + \binom{n}{n - n \mod 2} + n \mod 2 = \sum_{p = 0}^{\lfloor n/2 \rfloor} \binom{n}{2p} + n\mod 2$$$ways to pick the $$$1$$$st digit for all $$$a_i.$$$
Using the Binomial Theorem on $$$(1+1)^n$$$ and $$$(1-1)^n,$$$ we can show that $$$\sum_{p=0}^{\lfloor n/2 \rfloor} \binom{n}{2p} = 2^{n - 1}.$$$
Thus, the number of ways to pick the $$$1$$$st digit for all $$$a_i$$$ is $$$2^{n - 1} + n\mod 2.$$$ Similarly, this is the number of ways to pick the $$$j$$$th digit for all $$$a_i.$$$
Since there are $$$k$$$ digits total in each of $$$a_i,$$$ the answer is $$$(2^{n - 1} + n \mod 2)^k.$$$
My code describes this approach, and I think it performs this approach correctly. Thus, I believe my approach to the problem is incorrect. Can anyone point out what is wrong?
I have also attached by code in case it is wrong.
Thanks for the help everyone!!
My code#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
ll modpow(int x, int n, int m) {
if (n == 0) return 1 % m;
long long u = modpow(x, n / 2, m);
u = (u * u) % m;
if (n % 2 == 1) u = (u * x) % m;
return u;
}
void solve() {
int n, k; cin >> n >> k;
if(k == 0) {
cout << "1\n";
return;
}
long long ans = 1;
long long each = (modpow(2, n - 1, MOD1) + n % 2) % MOD1;
for(int i = 0; i < k; i++) {
// if n % 2 == 0 don't add anything
ans *= each;
ans %= MOD1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while(t--) {
solve();
}
}