ABC104 D - We Love ABC

問題

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

解法

Tの先頭i文字のABC数の和を求める方法を考えます。

のとき、i文字目は役に立たないので、Tの先頭i-1文字のABC数の和です。

のとき、i文字目を使わない場合、および、i文字目のCを使う場合の和なので、 （Tの先頭i-1文字のABC数）+（Tの先頭i-1文字のAB数）です。 ここで、AB数とは、以下の条件を満たす組(i, j)の個数です。

• 
• 
• 

のとき、i文字目をABCに含めない場合は?には3通りの好きな文字を入れられます。 i文字目をABCに含める場合はCを入れることになります。 したがって、3 * （Tの先頭i-1文字のABC数）+（Tの先頭i-1文字のAB数）です。

以上より、Tの先頭i-1文字のABC数とAB数が分かれば、O(1)でTの先頭i文字のABC数の和を求められます。 AB数も同様の考えで漸化式を導けます（AB数の和を求めるにはA数の和が必要。A数の和の漸化式は簡単でしょう）。

ABC数、AB数、A数の漸化式を導いたらi=1から順に|T|まで求めるだけです。

ACしたコード

from functools import reduce
M = 10**9 + 7
S = input()
ans = reduce(
    lambda t, s:
        (t[0], t[1] + t[0], t[2], t[3]) if s == 'A' else
        (t[0], t[1], t[1] + t[2], t[3]) if s == 'B' else
        (t[0], t[1], t[2], t[2] + t[3]) if s == 'C' else
        ((3 * t[0]) % M, (3 * t[1] + t[0]) % M, (3 * t[2] + t[1]) % M, (3 * t[3] + t[2]) % M),
    S,
    (1, 0, 0, 0)
)[3] % M
print(ans)