AT_abc418_d [ABC418D] XNOR Operation 题解

· · 题解

题意

给定长度为 N 的 01 串 S，求 S 有多少个不同位置的子串，使得：一直将它的相邻两位合并为按位同或的值，最后得到 1。

思路

定义 \operatorname{nor} 为按位同或，\operatorname{xor} 为按位异或，\neg 为按位取反。

设 x,y,z,p 都为 0 或 1。

根据定义有 x\operatorname{nor}y=\neg(x\operatorname{xor}y)。

易知 (\neg x)\operatorname{xor}y=\neg(x\operatorname{xor}y)，我叫它“异或分配率”，反过来依然成立。

因此

\begin{aligned} {}&x\operatorname{nor}y\operatorname{nor}z\\ =&\neg(\neg(x\operatorname{xor}y)\operatorname{xor}z)\\ =&\neg(\neg(x\operatorname{xor}y))\operatorname{xor}z\\ =&x\operatorname{xor}y\operatorname{xor}z \end{aligned}

于是

\begin{aligned} {}&x\operatorname{nor}y\operatorname{nor}z\operatorname{nor}p\\ {}&(x\operatorname{nor}y\operatorname{nor}z)\operatorname{nor}p\\ =&(x\operatorname{xor}y\operatorname{xor}z)\operatorname{nor}p\\ =&\neg((x\operatorname{xor}y\operatorname{xor}z)\operatorname{xor}p)\\ =&\neg(x\operatorname{xor}y\operatorname{xor}z\operatorname{xor}p) \end{aligned}

得出规律，奇数个 0 或 1 同或的结果是它们的异或，偶数个的结果是异或再取反。可以求出前缀异或和数组 s_i，则区间 [i,j] 的异或和是 s_i\operatorname{xor}s_{j-1}，同或和可以根据区间长度的奇偶性求出。

代码

#include <iostream>
using namespace std;
string st;
int n,a[200001],s[200001],cnt[2][2];
// cnt[x][y] 表示满足s[i]==y且i%2==x的i的数量
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>st;
    for(int i=1;i<=n;i++) {
        a[i]=st[i-1]-48;
        s[i]=s[i-1]^a[i]; // 前缀异或和
    }
    cnt[0][0]=1;
    long long ans=0;
    for(int i=1;i<=n;i++) {
        //    ↓长度为奇数       ↓长度为偶数
        ans+=cnt[i&1][s[i]]+cnt[(i&1)^1][s[i]^1];
        cnt[i&1][s[i]]++;
    }
    cout<<ans;
    return 0;
}