21 Days Training // Day (15 2/3)

D. XNOR Operation

The operator XNOR has under properties :

1. a xnor a = 1
2. (a xnor b) xnor c = a xnor (b xnor c)

It means that to get the XNOR sum of a region [L, R], we can first record the prefix XNOR sum, find the XNOR sum of [0, L] and [0, R], and XNOR the results again.

And, for this problem, the sequence has 1 more property :

All operations do not change the XNOR sum of the sequence.

So, if the XNOR sum of a sequence is 1, you can always operate properly to get the result of 1.

Therefore, we only need to count the number of substrings with the XNOR sum 1.

Using prefix sum, we only need to find the position pairs that have the same XNOR prefix sum.

Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;cin >> N;
    int XNORpfx[N+1];
    XNORpfx[0] = 1;
    long long ODc=1, EDc=0, c1=0;
    string S;cin >> S;
    for (int i=0;i<N;i++) {
        int I = S[i]-&#039;0&#039;;
        XNORpfx[i+1] = 1^(XNORpfx[i]^I);
        if (XNORpfx[i+1]) ODc++;
        else EDc++;
    }
    cout << (ODc*(ODc-1)/2)+(EDc*(EDc-1)/2);
    return 0;
}