ABC104 D - We Love ABC

解説ではDPが想定解。また他の記事にBを固定してA,C をカウントする方法もあったが、累積和を使っても比較的きれいにかける（実際には累積和しか浮かばなかった）。

解法

まず、Sの中からA, B, Cを選ぶときにたとえばAならAを選ぶ場合と?をAに変えてそれを選ぶ場合の2通りある。そのため3つの文字にどちらの方法で選ぶのか固定しChar(A)などと置く。 累積和SUM_C[i]をChar(C)がSのi番目以降で現れる個数とする。また、SUM_Bを部分列(Char(B), Char(C))がSのi番目以降で現れる個数、SUM_Aを部分列(Char(A), Char(B), Char(C))がSのi番目以降で現れる個数としておく。 すると、Char(-)を固定した場合には SUM_A[0] * 3^{使われていない'?'の個数} が答えになる。 あとはChar(-)を変えた8バターンを足し合わせればよい。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;


    ll N = S.size();
    vll res;
    rep(useQ, 0, 8) {
        vll Q(S.size() + 1);
        vll C(S.size() + 1);
        vll B(S.size() + 1);
        vll A(S.size() + 1);
        rrep(i, 0, N) {
            Q[i] = Q[i + 1] + (S[i] == '?' ? 1 : 0);
        }
        rrep(i, 0, N) {
            if (at_bit(useQ, 0)) {
                C[i] = (C[i + 1] + (S[i] == '?' ? 1 : 0)) % MOD;

            }
            else {
                C[i] = (C[i + 1] + (S[i] == 'C' ? 1 : 0)) % MOD;

            }

        }
        rrep(i, 0, N) {
            if (at_bit(useQ, 1)) {
                B[i] = (B[i + 1] +(S[i] == '?' ? C[i + 1] : 0)) % MOD;

            }
            else {
                B[i] = (B[i + 1] + (S[i] == 'B' ? C[i + 1] : 0)) % MOD;

            }

        }
        rrep(i, 0, N) {
            if (at_bit(useQ, 2)) {
                A[i] = (A[i + 1] +( S[i] == '?' ? B[i + 1] : 0)) % MOD;


            }
            else {
                A[i] = (A[i + 1] + (S[i] == 'A' ? B[i + 1] : 0)) % MOD;


            }
        }
        ll cntQ = Q[0] - (at_bit(useQ, 0) + at_bit(useQ, 1) + at_bit(useQ, 2));

        if (cntQ >= 0) {
            res.push_back((A[0] * POW_3(3LL, cntQ)) % MOD);

        }
    }

    ll out = 0;
    for (ll i : res)
        out = (out + i) % MOD;

    cout << out % MOD << endl;

    return 0;
}