We Love ABC [AtCoder Beginner Contest 104 D]

https://beta.atcoder.jp/contests/abc104/tasks/abc104_d

解法

https://beta.atcoder.jp/contests/abc104/submissions/2955573

配列から3要素順番にとって条件を満たす組合せ数というのは真ん中を固定して全探索というテクがある。
Bとなる要素を全探索する。
'B'か'?'ならBとなれるので、全探索しよう。
あるBについて、左の'A'の個数がla, 左の'?'の個数がlp、
右の'C'の個数がrc, 右の'?'の個数がrpとする。
これはBとなる要素を右に移しながら、減らしたり増やしたりして求めていこう。
　
あとは、la,lp,rc,rpが揃っている時にABCとなる組合せを数えることである。
問題では?に何かを入れた文字列を考えて、それから、それぞれABCの個数を数えるようにしているが、
逆にABCの位置を決めて、それがABCにちゃんとなる文字列が何通りあるかを数えることにする。
これは不確定な文字列に対する操作として典型の考え方である。
左側の組合せは2状況ある。
1. 'A'が書かれている要素をAの要素とする
　　Aの位置決め：la通り
　　それがAになる文字列：3^lp通り（他はどんな文字列でもよい）
2. '?'が書かれている要素をAの要素とする
　　Aの位置決め：lp通り
　　それがAになる文字列：3^(lp-1)通り（1つはAで確定していて、他は何でも良い）
この2つは独立であるため、足すと左側の組み合わせ数となる。
右側もほぼ同様に考えて組み合わせ数を出す。
あとは、左側と右側の組み合わせ数を足すとそのBとなる要素についての組み合わせ数が出る。
これを全て足し合わせると答え。
　
3の累乗は前計算しておくのが早いが、繰り返し二乗法で求めていっても良い
mod計算はライブラリ化しておくと、変な所でミスしないのでオススメ（遅くなるけど）

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
 
    mint ans = 0;
    int la = 0, lp = 0;
    int rc = 0, rp = 0;
 
    fore(c, S) {
        if (c == 'C') rc++;
        if (c == '?') rp++;
    }
 
    fore(c, S) {
        if (c == 'C') rc--;
        if (c == '?') rp--;
 
        if (c == '?' or c == 'B') {
            mint l = mint(la) * (mint(3) ^ lp) + mint(lp) * (mint(3) ^ (lp - 1));
            mint r = mint(rc) * (mint(3) ^ rp) + mint(rp) * (mint(3) ^ (rp - 1));
            ans += l * r;
        }
 
        if (c == 'A') la++;
        if (c == '?') lp++;
    }
 
    cout << ans << endl;
}