PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Akash Tike
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
Binary operations, modular arithmetics
PROBLEM:
You’re given two binary strings A and B of length N. Let A' and B' be strings A and B shuffled in some specific way. Calculate the number of distinct possible values of their xor A' \oplus B'.
QUICK EXPLANATION:
consider minimum and maximum number of ones in A' \oplus B' you can obtain. Any number of ones between them with the same parity can be achieved.
EXPLANATION:
First of all, since the order of ones and zeros in the input doesn’t matter, we may assume that the answer is determined by the number of ones in given strings. Let it be N_A and N_B for strings A and B correspondingly. It’s quite easy to see that minimum possible number of ones in A' \oplus B' is L=|N_A-N_B| since we may sort both A and B.
And the maximum number of ones is R=|N_A+N_B-2 \cdot \max(0, N_A + N_B - N)| since we may put N_A ones in the beginning of A' and N_B ones in the end of B'. If N_A+N_B > N then their intersection is of the size (N_A+N_B-N) so we should double subtract it to get the symmetric difference of the sets of positions of ones in A' and B'.
Gradually shifting starting position of the block of ones in B' we may obtain any intermediary (with same parity) number of ones in A' \oplus B' and applying same permutation to both A' and B' we may rearrange them in any way. Note that the parity of ones in A' \oplus B' is invariant and determined by the parity of the number of ones in A' and B' only, thus it constitutes all possible answers. That being said, we have to sum up \binom{N}{k} with k going from L to R with the step of 2:
void solve() {
int N;
cin >> N;
string A, B;
cin >> A >> B;
int Na = count(begin(A), end(A), '1');
int Nb = count(begin(B), end(B), '1');
int ans = 0;
int L = abs(Na - Nb);
int R = Na + Nb - 2 * max(0, Na + Nb - N);
for(int k = L; k <= R; k += 2) {
ans = (ans + nCr(N, k)) % mod;
}
cout << ans << endl;
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.
Editorialist’s solution can be found here.