本解説執筆時点の MMNMM に recognizable series の知見がほとんどなく、本問題がこの方針で解けることへの天下りでも ad-hoc でもない証明ができていません。 できた場合、追記を行います。

えこってさんによって提案された、文字列をキーとするある種の DP について、愚直解法を経由して一部の実装をスキップする手法があります。 えこってさんの手法では、文字列 \(S\) に対する答え \(f(S)\) が、ある自然数 \(n\) と \(n\) 次元ベクトル \(u,v\) および文字から \(n\) 次正方行列への写像 \(p\) を用いて \[f(S)=u ^ {\top}\prod _ {i=1} ^ Np(S _ i)v\] と書けるとき（このような \(f\) （から定まる形式的級数）を recognizable series というそうです この解説では \(f\) を recognizable であるということにします）、短い \(S\) に対する \(f(S)\) の値から、この \(u,v,f\) を具体的な形で得ることができます。

詳細はこちらの maspy さんによる記事を参考にしてください。

この問題の設定において、任意の \((A,B,C,D)\) に対して美しい文字列全体は正則言語となるため、美しい部分文字列の個数が recognizable であることはすぐわかります（美しい文字列を受理する決定性有限オートマトンに対して DP を行うことを考えると、各状態に対する遷移が現在見ている文字に対応する行列として書けることがわかります）。 一方、美しい部分文字列の最長の長さが recognizable になることは明らかではなく、実際いくつかの \((A,B,C,D)\) の組に対しては recognizable ではありません。 しかし、recognizable でない \((A,B,C,D)\) は \(16\) 個の問題のうち \(3\) つしかなく、それらも簡単な考察で解くことができます。

実装例は以下のようになります。 オートマトンの大きさ程度の次元の行列とベクトルの積を利用するため、想定解法より少し計算量が悪くなっていることに注意してください。

#include <iostream>
#include <array>
#include <numeric>
#include <algorithm>
#include <atcoder/modint>

// modint を絶対値が最小となる代表元で出力する
namespace atcoder {
    template<int m>
    std::ostream& operator<<(std::ostream& os, const static_modint<m>& x) {
        if (x.val() * 2 < m)
            os << x.val();
        else
            os << '-' << (-x).val();
        return os;
    }
}

// recognizable な関数の表現から S に対する値を求める
template<typename T, size_t N, size_t M>
T matrix_solve(const std::string& S, const std::array<std::array<std::array<T, N>, N>, M>& char_coefficients, const std::array<T, N>& initial_vector) {
    std::array<T, N> dp{1};
    for (const char c : S) {
        std::array<T, N> z{};
        for (size_t i{}; i < N; i++)
            for (size_t j{}; j < N; j++)
                z[i] += dp[j] * char_coefficients[c - '0'][j][i];
        dp = z;
    }
    return std::inner_product(begin(dp), end(dp), begin(initial_vector), T{});
}

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;
    string S;
    cin >> S >> S;
    // 0000 length
    cout << matrix_solve<modint, 2, 2>(S, {{{{{1, 0}, {0, 1}}}, {{{0, 1}, {0, 1}}}}}, {-1, 1}) << " ";
    // 0000 count
    cout << matrix_solve<long, 2, 2>(S, {{{{{1, 0}, {0, 1}}}, {{{0, 1}, {-1, 2}}}}}, {0, 1}) << endl;
    // 0001 length
    cout << [](const string& S) -> int {
        unsigned ans{}, tmp{};
        for (const auto c : S) {
            if (c == '1')
                ++tmp;
            else
                tmp = 0;
            ans = max(ans, tmp);
        }
        return ans - !ans;
    }(S) << " ";
    // 0001 count
    cout << matrix_solve<long, 3, 2>(S, {{{{{1, 0, 0}, {0, 0, 1}, {0, 0, 1}}}, {{{0, 1, 0}, {-2, 2, 1}, {-1, 1, 1}}}}}, {0, 1, 1}) << endl;
    // 0010 length
    cout << matrix_solve<modint, 5, 2>(S, {{{{{1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, -1, 1, 1}, {0, 0, -1, 0, 2}}}, {{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 1}, {0, 0, -1, 0, 2}}}}}, {-1, 1, 2, 1, 3}) << " ";
    // 0010 count
    cout << matrix_solve<long, 5, 2>(S, {{{{{1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 1}, {0, -1, 1, 1, 0}, {0, 0, -1, 0, 2}}}, {{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {-1, 1, 0, 0, 1}, {-1, 0, 1, 1, 0}, {-1, 1, -1, 0, 2}}}}}, {0, 1, 2, 2, 3}) << endl;
    // 0011 length
    cout << matrix_solve<modint, 3, 2>(S, {{{{{1, 0, 0}, {0, 0, 1}, {0, -1, 2}}}, {{{0, 1, 0}, {0, 0, 1}, {0, -1, 2}}}}}, {-1, 1, 2}) << " ";
    // 0011 count
    cout << matrix_solve<long, 3, 2>(S, {{{{{1, 0, 0}, {0, 0, 1}, {0, -1, 2}}}, {{{0, 1, 0}, {-1, 1, 1}, {-1, 0, 2}}}}}, {0, 1, 2}) << endl;
    // 0100 length
    cout << matrix_solve<modint, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {-1, 2, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, -1, 1, 1}, {-1, 1, 0, 0, 1}}}, {{{0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, -1, 1, 1}, {1, -1, -2, 2, 1}}}}}, {-1, -1, 1, 2, 1}) << " ";
    // 0100 count
    cout << matrix_solve<long, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {-1, 2, 0, 0, 0}, {0, 0, 0, 1, 0}, {-1, 1, 0, 1, 0}, {1, -1, -2, 2, 1}}}, {{{0, 0, 1, 0, 0}, {-1, 0, 2, 0, 0}, {0, -1, 1, 1, 0}, {0, 0, 0, 0, 1}, {2, -1, -3, 1, 2}}}}}, {0, 0, 1, 1, 4}) << endl;
    // 0101 length
    cout << matrix_solve<modint, 3, 2>(S, {{{{{0, 1, 0}, {-1, 2, 0}, {-1, 1, 1}}}, {{{0, 0, 1}, {-1, -499122176, -499122175}, {-1, -499122176, -499122175}}}}}, {-1, -1, 1}) << " ";
    // 0101 count
    cout << matrix_solve<long, 3, 2>(S, {{{{{0, 1, 0}, {-1, 2, 0}, {-1, 1, 1}}}, {{{0, 0, 1}, {-1, 0, 2}, {-1, -1, 3}}}}}, {0, 0, 1}) << endl;
    // 0110 length
    cout << [](const string& S) -> int {
        const auto ones{ranges::count(S, '1')};
        if (ones == 0)
            return -1;
        if (ones & 1)
            return size(S);
        return max(S.find_last_of('1'), size(S) - S.find_first_of('1') - 1);
    }(S) << " ";
    // 0110 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {-1, 2, 0, 0}, {0, 0, 0, 1}, {0, 0, -1, 2}}}, {{{0, 0, 1, 0}, {-1, 0, 2, 0}, {0, 0, 0, 1}, {0, -1, 0, 2}}}}}, {0, 0, 1, 2}) << endl;
    // 0111 length
    cout << matrix_solve<modint, 4, 2>(S, {{{{{0, 1, 0, 0}, {-1, 2, 0, 0}, {0, 0, 0, 1}, {0, 0, -1, 2}}}, {{{0, 0, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, -1, 2}}}}}, {-1, -1, 1, 2}) << " ";
    // 0111 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {-1, 2, 0, 0}, {0, 0, 0, 1}, {0, 0, -1, 2}}}, {{{0, 0, 1, 0}, {-1, 0, 2, 0}, {0, -1, 1, 1}, {0, -2, 1, 2}}}}}, {0, 0, 1, 2}) << endl;
    // 1000 length
    cout << matrix_solve<modint, 8, 2>(S, {{{{{0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, -1, 0, 1, 1}, {0, 0, 0, 0, -1, 0, 1, 1}}}, {{{0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 2, -1}, {0, 0, 0, 0, -1, 0, 1, 1}, {0, 0, 0, 0, -1, 0, 1, 1}}}}}, {-1, -1, 1, 2, 1, 1, 2, 3}) << " ";
    // 1000 count
    cout << matrix_solve<long, 7, 2>(S, {{{{{0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, -1, 0, 1, 1}, {0, 0, 1, -1, -1, 0, 2}, {0, 0, 1, -2, -1, 0, 3}}}, {{{0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0}, {0, -1, 1, 0, 0, 1, 0}, {0, 0, 1, -2, 0, 0, 2}, {0, -1, 1, -1, 0, 1, 1}, {0, 0, 0, -1, 1, 0, 1}, {0, 0, 2, -4, -1, 0, 4}}}}}, {0, 0, 1, 1, 1, 1, 2}) << endl;
    // 1001 length
    cout << [](const string& S) -> int {
        if (S == "0")
            return -1;
        const auto zeros{ranges::count(S, '0')};
        if (~zeros & 1)
            return size(S);
        return max(S.find_last_of('0'), size(S) - S.find_first_of('0') - 1);
    }(S) << " ";
    // 1001 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {-1, 1, 1, 0}, {0, 0, 0, 1}, {-1, -1, 2, 1}}}, {{{0, 0, 1, 0}, {-1, 1, 1, 0}, {0, -2, 2, 1}, {-1, 0, 1, 1}}}}}, {0, 0, 1, 1}) << endl;
    // 1010 length
    cout << matrix_solve<modint, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, -1, 2}}}, {{{0, 0, 1, 0, 0}, {0, -499122176, 499122176, 1, 0}, {0, -499122176, 499122176, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, -1, 2}}}}}, {-1, -1, 1, 2, 3}) << " ";
    // 1010 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {0, 0, 0, 1}, {0, -1, 1, 1}, {0, -2, 1, 2}}}, {{{0, 0, 1, 0}, {0, 0, 0, 1}, {0, -1, 1, 1}, {0, -2, 1, 2}}}}}, {0, 0, 1, 1}) << endl;
    // 1011 length
    cout << matrix_solve<modint, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 1, 0}, {0, 0, -1, 2, 0}, {0, 0, -1, 2, 0}}}, {{{0, 0, 1, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0}, {0, 0, -1, 2, 0}, {0, 0, -1, 1, 1}}}}}, {-1, -1, 1, 2, 1}) << " ";
    // 1011 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {-1, 1, 1, 0}, {0, 0, 0, 1}, {0, -1, 0, 2}}}, {{{0, 0, 1, 0}, {-1, 1, 1, 0}, {0, -1, 1, 1}, {0, -1, 0, 2}}}}}, {0, 0, 1, 2}) << endl;
    // 1100 length
    cout << matrix_solve<modint, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, -1, 0, 0, 2}, {0, -1, 0, 0, 2}}}, {{{0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, -1, 0, 0, 2}, {0, -1, 0, 0, 2}}}}}, {-1, -1, 1, 2, 1}) << " ";
    // 1100 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {1, -3, 0, 3}}}, {{{0, 0, 1, 0}, {0, -1, 1, 1}, {0, -1, 1, 1}, {1, -4, 1, 3}}}}}, {0, 0, 1, 1}) << endl;
    // 1101 length
    cout << matrix_solve<modint, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, -1, 0, 0, 2}, {0, -1, 0, 0, 2}}}, {{{0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, -1, 1, -1, 2}, {0, -1, 0, 0, 2}, {0, -1, 0, 0, 2}}}}}, {-1, -1, 1, 2, 1}) << " ";
    // 1101 count
    cout << matrix_solve<long, 4, 2>(S, {{{{{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {1, -3, 0, 3}}}, {{{0, 0, 1, 0}, {0, -1, 1, 1}, {0, -2, 2, 1}, {1, -4, 1, 3}}}}}, {0, 0, 1, 1}) << endl;
    // 1110 length
    cout << matrix_solve<modint, 6, 2>(S, {{{{{0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, -1, 0, 0, 0, 2}, {0, -1, 0, 0, 0, 2}, {0, -1, 0, 0, 0, 2}}}, {{{0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1}, {0, -1, 0, 0, 0, 2}, {0, -1, 0, -1, 0, 3}, {0, -1, 0, 0, 0, 2}}}}}, {-1, -1, 1, 2, 2, 1}) << " ";
    // 1110 count
    cout << matrix_solve<long, 5, 2>(S, {{{{{0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {1, -3, 0, 3, 0}, {2, -5, 0, 4, 0}}}, {{{0, 0, 1, 0, 0}, {0, -1, 1, 1, 0}, {0, -1, 1, 1, 0}, {1, -4, 1, 3, 0}, {1, -4, 1, 3, 0}}}}}, {0, 0, 1, 1, 2}) << endl;
    // 1111 length
    cout << matrix_solve<modint, 4, 2>(S, {{{{{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, -1, 2}}}, {{{0, 0, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, -1, 2}}}}}, {-1, -1, 1, 2}) << " ";
    // 1111 count
    cout << matrix_solve<long, 3, 2>(S, {{{{{0, 1, 0}, {-1, 1, 1}, {-1, 0, 2}}}, {{{0, 0, 1}, {-1, 0, 2}, {-1, -1, 3}}}}}, {0, 0, 1}) << endl;
    return 0;
}