ABC104 D. We Love ABC

問題

文字列TのABC数を以下の条件を満たす整数の組(i,j,k)の個数とする。

• 1 <= i < j < k <= |T|
• T_i = 'A'
• T_j = 'B'
• T_k = 'C'

文字列Sが与えられるが、SはA,B,C,?の4つの文字からなり、?は、AまたはBまたはCに展開した文字列を考える。
?がQ個あった場合は、3^Q個の文字列に対し、それぞれのABC数の和を求めよ。
和は10^9+7で割ったあまりで求めよ。

制約

• 3 <= |S| <= 10^5

解法

「どのA,B,Cを選択したか？」というのを区別する必要がある。

したがって、
dp[i][j][k] := i文字目までで、選択したABCの個数がj個で、最後の文字がkである通り数
のように、選択した個数を状態にしたdpを考えてあげれば良い。

(どれを選択したかは覚えておく必要がなく、すでにAまで選択したか？すでにBまで選択したか？すでにCまで選択したか？がわかればよい。)

i番目がAまたは?である場合、
// そのAを選択しない
dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
// そのAを選択する
dp[i][1][0] += dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]

i番目がBまたは?である場合は、
// そのBを選択しない
dp[i][j][1] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
// そのBを選択する
dp[i][2][1] += dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]

i番目がCまたは?である場合は、
// そのCを選択しない
dp[i][j][2] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
// そのCを選択する
dp[i][3][2] += dp[i-1][2][0] + dp[i-1][2][1] + dp[i-1][2][2]

のような更新を行えばよい。
答えは、Σ_{k=0,1,2} dp[|S|][3][k]で求められる。