まずは文字列 \(S\) が美しい文字列である条件を発見しましょう。
この手の文字列や数列に対して操作を行う問題に取り組む場合は、不変量 (操作の前後で変わらない何らかの値) を探すアプローチが有効になることが多いです。
これを踏まえて操作を観察します。 0 の個数に注目しましょう。

• 00 を 1 に変化させると、0 の個数は 2 個減る。
• 01 を 0 に変化させると、0 の個数は変わらない。
• 10 を 0 に変化させると、0 の個数は変わらない。
• 11 を 1 に変化させると、0 の個数は変わらない。

操作によって \(0\) の個数は変わらないか 2 個減ることがわかります。ここから、操作によって 0 の個数の偶奇は不変である ということが発見できます。
\(S\) が美しい文字列であるためには最終的に \(S=\) 1 である必要があります。1 は 0 を偶数個含む文字列です。よって上記の不変量を踏まえると、

• \(S\) が 0 を偶数個含む非空な文字列であれば美しい文字列であり、
• \(S\) が 0 を奇数個含む非空な文字列であれば美しい文字列ではない

ということが証明できます。以上より美しい文字列の条件を数え上げやすい形に言い換えることが出来ました。

次は \(T\) に部分文字列として含まれる美しい文字列、すなわち 0 を偶数個含む非空な文字列の個数を数えましょう。
\(S\) の \(i\) 文字目から \(j\) 文字目をまでを取り出してできる文字列を \(S[i,j]\) と表します。DP の状態を次のように置きます。

• \(\mathrm{dp}_{r,0}\) : \(S[1,r], S[2,r], \dots, S[r,r]\) のうち 0 を偶数個含む文字列の個数
• \(\mathrm{dp}_{r,1}\) : \(S[1,r], S[2,r], \dots, S[r,r]\) のうち 0 を奇数個含む文字列の個数

このように定義すると、\(\mathrm{dp}_{r,0}, \mathrm{dp}_{r,1}\) および \(S_{r+1}\) の文字の種類から \(\mathrm{dp}_{r+1,0}, \mathrm{dp}_{r+1,1}\) を計算できることがわかります。また、問題の答えは \(\sum_{r=1}^N \mathrm{dp}_{r,0}\) です。
よってこの問題を動的計画法で \(\mathrm{O}(N)\) で解くことが出来て、これは十分高速です。

• 実装例(C++)

#include <iostream>
#include <string>
using namespace std;

constexpr int nmax = 2e5 + 10;
int dp[nmax][2];

int main() {
  int N;
  string S;
  cin >> N >> S;
  for (int r = 1; r <= N; r++) {
    if (S[r - 1] == '0') {
      dp[r][0] = dp[r - 1][1];
      dp[r][1] = dp[r - 1][0] + 1;
    } else {
      dp[r][0] = dp[r - 1][0] + 1;
      dp[r][1] = dp[r - 1][1];
    }
  }
  long long ans = 0;
  for (int r = 1; r <= N; r++) ans += dp[r][0];
  cout << ans << "\n";
}