怎么都是 dp 做的，就我是手玩出来的吗/oh。
首先关于 \(\operatorname{NAND}\) 有一个经典技巧：\(x\barwedge 0=1,x\barwedge 1=\neg x\)。
发现一个 \(0\) 会将值强制置 \(1\)，而一个 \(1\) 会将值取反，于是 \(f(l,r)\) 的值只取决于区间内最后一个 \(0\) 后 \(1\) 的数量。
注意到 \(n\) 个 \(1\) 依次 \(\operatorname{NAND}\) 的值为 \(n\bmod 2\)。
考虑枚举 \(r\)，对 \(S_r\) 分类讨论：
- 若 \(S_r=\mathtt{0}\)：那么对所有 \(l\in[1,r)\)，不管前面得到了什么值，最后 \(x\barwedge S_r\) 都能得到 \(1\)，于是贡献为 \(r-1\)。注意 \(l=r\) 时 \(f(r,r)=0\)，没有贡献；
- 若 \(S_r=\mathtt{1}\)：考虑维护连续 \(1\) 的个数，记作 \(c\)。那么每出现一个 \(1\)，得到的值会取反，所以有：
- 在 \(l\in(r-c,r]\) 中，\(1,0\) 交替出现，贡献为 \(\lceil\frac{c}{2}\rceil\)；
- 对于 \(l=r-c\)，由于 \(0\barwedge 1=1\)，所以 \(f(l,r)\) 即为 \(c\) 个 \(1\) 依次 \(\operatorname{NAND}\) 的值，即 \(c\bmod 2\)；
- 对于 \(l\in[1,r-c)\)，由于位于 \(S_{r-c}\) 的 \(0\) 总能将前面的值变成 \(1\)，所以 \(f(l,r)\) 为 \(c+1\) 个 \(1\) 依次 \(\operatorname{NAND}\) 的值，即 \((c+1)\bmod 2\)，总贡献为 \(((c+1)\bmod 2)\times(r-c-1)\)。
\(c\) 的维护是 trival 的，于是我们就能在 \(\mathcal{O}(n)\) 的时间内求出答案了。
#include <iostream>
using namespace std;
using LL = long long;
int n;
LL ans;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int r = 1, c = 0; r <= n; ++r) {
char ch;
cin >> ch;
if (ch == '0') {
c = 0;
ans += r - 1;
} else {
++c;
ans += (c + 1) / 2;
if (r > c) { // 判断 r-c 是否存在
ans += c & 1;
ans += (c + 1 & 1) * (r - c - 1);
}
}
}
cout << ans;
return 0;
}