E- NAND repeatedly

問題

を求めよ。
ただし、　である

考えてたこと

・二重和なので、一度全体の和を求めて、いい感じに調整して回計算するのだろうなという予測を立てる
・否定論理積の性質から、の値は0または1のどちらかである。
・ここで、 は、先程の式から一つ前の値と文字の値で決まる。つまり、文字目は直前の値の種類だけ状態数がある。
・一つ前の値がとしたときの、から番目までの累積和を計算して、この２つで累積和の値をメモ化しておく。
・あとは一つ目の和をループして終わり。

#include <bits/stdc++.h>

using namespace std;
using Int = long long;
int N;
string s;

Int rec(int idx, int pbit,vector<vector<Int>>&memo, vector<vector<bool>>&used, vector<int>&A){
    if(used[idx][pbit]){
        return memo[idx][pbit];
    }
    used[idx][pbit] = true;
    return memo[idx][pbit] = (idx + 1 < N ? rec(idx + 1,!(pbit && A[idx]),memo,used,A) : 0) + !(pbit && A[idx]);
}

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N; cin >> s;
    vector<int>A;
    for(auto c : s) A.push_back(c - '0');
    vector<vector<Int>>memo(N,vector<Int>(2,0LL));
    vector<vector<bool>>used(N, vector<bool>(2,false));
    
    Int ans = 0;
    for(int i = 0; i < N; ++i){
        ans += A[i] + (i + 1 < N ? rec(i + 1,A[i],memo,used,A) : 0);
    }
    cout << ans << endl;
    
}

感想

解放までは５分だったけど、累積和の書き方でこじらせた。