B. The Bits

길이 n인 2진수 a,b가 주어지고

2진수 a에서 i,j번째 bit를 swap한 2진수를 a'라고 할 때

a | b != a' | b 를 만족하게 하는 i,j 쌍의 개수를 출력하는 문제다.

케이스를 나눠보자

1.

a[i] = 0

b[i] = 0일 때

a[j]와 swap해서 기존과 값이 달라지려면 a[i] | b[i] == 0이므로

a[i] | b[i] = 1로 변하던지 a[j] | b[j] = 0 으로 변하는 경우다.

a[j] = 1

b[j] = 0 || b[j] = 1

두가지 경우가 있다.

2.

a[i] = 0

b[i] = 1일 때

a[i] | b[i] == 1이므로

a[j] = 1

b[j] = 0

한가지 경우가 있다.

3. 

a[i] = 1

b[i] = 0일 때

a[j] = 0

b[j] = 0 || b[j] = 1

두가지 경우

4. 

a[i] = 1

b[i] = 1일 때

a[j] = 0

b[j] = 0

한가지 경우가 있다. 각 케이스별 누적합을 사용해 계산하는 방법을 사용했다.

중복카운트를 피하기 위해 i번째 위치에선 i+1~n범위에서 찾는다.

#include <iostream>
using namespace std;
 
typedef long long ll;
 
int n;
char a[100001], b[100001];
int d[100001][4];
ll ans;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    cin >> a + 1 >> b + 1;
    for (int i = 1; i <= n; ++i) {
        int c = ((a[i] - '0') << 1) + b[i] - '0';
        for (int j = 0; j < 4; ++j)
            d[i][j] = d[i - 1][j];
        d[i][c]++;
    }
    for (int i = 1; i <= n; ++i) {
        int c = ((a[i] - '0') << 1) + b[i] - '0';
        if (c == 0) {
            ans += (d[n][2] - d[i][2]) + (d[n][3] - d[i][3]);
        }
        else if (c == 1) {
            ans += (d[n][2] - d[i][2]);
        }
        else if (c == 2) {
            ans += (d[n][0] - d[i][0]) + (d[n][1] - d[i][1]);
        }
        else {
            ans += (d[n][0] - d[i][0]);
        }
    }
    cout << ans;
    return 0;
}