まず、次のような \(\Theta(N^2)\) 時間の解法を考えます。

はじめ、\(S=(),\operatorname{ans}=0\) とする。 \(i=1,2,\ldots,N\) に対して、次の操作を行う。

• \(S\leftarrow(s_j\barwedge A _ i) _ {j=1,2,\ldots,i-1}\mathbin{+\mkern-10mu+}A _ i\) とする。ここで、\(s _ j\) は \(S\) の \(j\) 番目の要素、\(\mathbin{+\mkern-10mu+}\) は列の連結を表す。
• \(\operatorname{ans}\leftarrow\operatorname{ans}+\sum _ {j=1} ^ {i} s_j\) とする。

このアルゴリズムが終了したときの \(\operatorname{ans}\) は正しい答えを与えますが、実行時間制限に間に合いません。

ここで、\(S\) はつねに \(\{0,1\}\) の要素しか含まないことを利用します。 \(S\) に \(0\) がいくつ、\(1\) がいくつ含まれているかを管理することで、この問題を \(\Theta(N)\) 時間で解くことができます。

実装例は以下のようになります。

N = int(input())
A = input()

zero, one = 0, 0
ans = 0

for a in A:
    if a == '0':
        zero, one = 1, zero + one
    else:
        zero, one = one, zero + 1
    ans += one

print(ans)

#include <vector>
#include <iostream>
#include <utility>

int main() {
    using namespace std;

    unsigned long N;
    cin >> N;
    vector<char> A(N);
    for (auto &&a : A)cin >> a;

    unsigned long ans{};

    using count_t = pair<unsigned long, unsigned long>;
    count_t counter{};
    auto&&[zero, one]{counter};

    for (const auto a : A) {
        counter = a == '1' ? count_t{one, zero + 1} : count_t{1, one + zero};
        ans += one;
    }

    cout << ans << endl;

    return 0;
}