[Solved] Equal Hamming Distance CodeChef Starters 75

Chef is given two binary strings A and B, each having length N.

Chef wants to find the number of binary strings �C, of length �N, such that �(�,�)=�(�,�)H(A,C)=H(B,C), where �(�,�)H(X,Y) denotes the hamming distance between the strings �X and �Y.

Since the answer can be large, output it modulo 109+7109+7.

Note: Hamming distance between two strings of equal length is the number of positions at which the corresponding characters are different.

Input Format

• The first line of input will contain a single integer �T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains a single integer �N, the length of the strings.
  • The second line contains the binary string �A.
  • The third line contains the binary string �B.

Output Format

For each test case, output in a new line, the number of binary strings �C which satisfy the given conditions modulo 109+7109+7.

Constraints

• 1≤�≤10001≤T≤1000
• 1≤�≤2⋅1051≤N≤2⋅105
• �A and �B consist of 00 and 11 only.
• Sum of �N over all test cases do not exceed 2⋅1052⋅105.

Sample 1:

Input

3
2
11
00
5
10101
10101
3
101
011

Output

2
32
4

Explanation:

Test case 11: The number of strings �C, of length 22, such that �(�,�)=�(�,�)H(A,C)=H(B,C) is 22. The strings are:

• �=10C=10: Here, �(11,10)=�(00,10)=1H(11,10)=H(00,10)=1, as there is only one position where the corresponding characters are different.
• �=01C=01: Here, �(11,01)=�(00,01)=1H(11,01)=H(00,01)=1.

Test case 33: The number of strings �C, of length 33, such that �(�,�)=�(�,�)H(A,C)=H(B,C) is 44. The strings are:

• �=000C=000: Here, �(101,000)=�(011,000)=2H(101,000)=H(011,000)=2, as there are two positions where the corresponding characters are different.
• �=111C=111: Here, �(101,111)=�(011,111)=1H(101,111)=H(011,111)=1, as there is only one position where the corresponding characters are different.
• �=001C=001: Here, �(101,001)=�(011,001)=1H(101,001)=H(011,001)=1, as there is only one position where the corresponding characters are different.
• �=110C=110: Here, �(101,110)=�(011,110)=2H(101,110)=H(011,110)=2, as there are two positions where the corresponding characters are different.

Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007

int mul(int a, int b) {
    return (a * b) % mod;
}

int binpow(int a, int b) {
    if (b == 0) return 1;
    int res = binpow(a, b / 2);
    res = mul(res, res);
    if (b % 2) res = mul(res, a);
    return res;
}

int modinv(int a, int m=mod) {
    return binpow(a, m - 2);
}

const int sz = 2e5 + 1;
int factorize[sz], invfact[sz];

void pre() {
    factorize[0] = invfact[0] = 1;
    for (int i = 1; i < sz; i++) {
        factorize[i] = mul(factorize[i - 1], i);
        invfact[i] =mul(invfact[i - 1], modinv(i));
    }
}


void solve(){
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) count++;
    }
    if((n - count) % 2) {
        cout << 0 << endl;
        return;
    }

    n = n - count;
    int result = binpow(2, count);
    result = mul(result, mul(factorize[n], mul(invfact[n / 2], invfact[n / 2])));
    cout << result << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Happy Learning – If you require any further information, feel free to contact me.