ABC104 D - We Love ABC

AtCoder Beginner Contest
問題

"ABC?" の4文字のみからなる文字列sが与えられる
この文字列が '?' をq個含むとき、それらの '?' を "ABC" のいずれかに置き換えることで3^q個の文字列が作られる
それぞれの文字列に含まれるABC数の和を求める
(ABC数: 文字列から3文字抜き取って左から順に読むと"ABC"となるような抜き取り方の数)

3 <= |s| <= 10^5

解法

「3箇所選ぶ」といえば真ん中を固定するのが典型テクニック
Bを固定して、左のAと右のCがそれぞれ何通りあり得るかわかればそれらの積を足していけばいい

あるBの左側にAがla個、?がlq個あるとき、
la個あるAのうちどれかをAとして使うときは、lq個ある?はそれぞれ何でもいいから、そのAと今見ているBを使うような場合は3^lq通りある
一方lq個ある?のうちどれかをAとして使うときは、残りlq-1個の?が何でもいいから3^(lq-1)通り
これらの和と、同様にして'C'としてあり得る数を求めたものの積を答えに足していく

公式の解説は後ろから埋めるDP
DPでも解けそうとは思ったけど俺的には真ん中固定の方が自然に感じる

実装

mop(a,b)ってのは二分累乗でaのb乗を求めるやつ

#define int long long

string s;
int res, la, lq, rc, rq;

signed main() {
	cin >> s;
	rc = count(all(s),'C'), rq = count(all(s),'?');
	each(i,s) {
		if (i=='C') rc--;
		if (i=='?') rq--;
		if (i=='B' || i=='?') {
			int l = (la*mop(3,lq) + lq*mop(3,lq-1))%mod,
				r = (rc*mop(3,rq) + rq*mop(3,rq-1))%mod;
			(res += l*r) %= mod;
		}
		if (i=='A') la++;
		if (i=='?') lq++;
	}
	cout << res << endl;
}