区間の数え上げ． 最初に考えたのは，\(x nand y = 0\) になる \(x,y \in 2\) の方が少ないから， 取り方全体から\(0\)になる取り方を除く方針だった． 区間 \([l,r]\) の nand が\(0\) になるケースは， \(r\)が \(1\) かつ \([l,r-1]\) までの nand が \(1\)であること が必要十分． よって，dp で全探索をするのが良さそう．
DP
\(r \in N, x \in 2\) を任意にとる． ある \(0 \leq l \leq r\) が存在して， 区間 \([l,r]\) の \(s\) に対する nand が \(x\) になる場合の数 を \(dp_{r,x}\) とおく．
場合分けで数える． 各 \(r \in N\) に対して， \(s_{r}\) を使うと仮定してそれぞれ求める． \(s_{r-1}\) を使う場合と使わない場合に場合分けして考える．
注意
nand は可換だが， 結合法則は成り立たないし， 単位元も存在しない． 特に，dp の初期化に注意．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
string s; cin >> s;
ll ans = 0;
// とくに，空の区間に対する適切な答えに注意．
// 安全に行くなら，閉区間で考えたい．
// rem: 結合法則も成り立たない．
// [l,r]
rep(r,n){
swap(dp,old);
// dp[r] = [0,r) までの ans
// s[r] を使うとする
if(s[r] == '0'){
// s[r-1]を使う
dp[1] += old[0];
dp[1] += old[1];
// 使わない
dp[0] += 1;
}else{
// s[r-1]を使う
dp[1] += old[0];
dp[0] += old[1];
// 使わない
dp[1] += 1;
}
ans += dp[1];
}
cout << ans << endl;
return 0;
}
