https://ac.nowcoder.com/acm/contest/331/F

题解：

std

引理：如果一个子矩形的字符串可以单独重组成为回文串，那么其出现奇数个的字符至多只有一个。

考虑状压数字的每一位，第i位为1表示i出现次数为奇数次。

基于上面的引理，我们可以从左到右维护矩形前缀异或和。

当子矩形异或和的二进制表示只有1个或者0个1位时，该子矩形能单独重组成为回文串。

具体做法类似于求前缀和满足条件的计数，将第一行、第二行和两行一起三种情况分开即可。

设可以选用的字符大小集为S，时间复杂度为O(S*N)或O(NlogN)O(Nlog⁡N)（不同的实现方法）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int mn = 1e6 + 5;
 
int n;
char a[mn], b[mn];
 
ll ca[mn], cb[mn], c[mn];
int ha[mn], hb[mn], h[mn];
int main() {
    scanf("%d", &n);
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    ll ans = 0;
    ca[0] = cb[0] = c[0] = 1;
    for (int i = 1; i <= n; i++) {
        ha[i] = ha[i - 1] ^ (1 << (a[i] - '0'));
        hb[i] = hb[i - 1] ^ (1 << (b[i] - '0'));
        h[i] = h[i - 1] ^ (1 << (a[i] - '0')) ^ (1 << (b[i] - '0'));
 
        ans += c[h[i]] + ca[ha[i]] + cb[hb[i]];
        for (int j = 0; j <= 9; j++) {
            ans += ca[ha[i] ^ (1 << j)] + cb[hb[i] ^ (1 << j)] +
                   c[h[i] ^ (1 << j)];
        }
 
        ca[ha[i]]++;
        cb[hb[i]]++;
        c[h[i]]++;
    }
    printf("%lld\n", ans);
}