Problem p03291 (python)

Fixed submission:
# -*- coding: utf-8 -*-

"""
参考：http://drken1215.hatenablog.com/entry/2018/08/05/224100_1
・文字列DP
・こういう、ちょっと状況込み入ったDPがまだ自分でうまく書けない。
・もっと数こなして経験積まなきゃなー。
"""

MOD = 10 ** 9 + 7
S = input()

# 文字列Sのi文字目まで考えたときにABCのj文字目まで照合させた個数
dp = [[0] * 4 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    # i文字目でABCカウントを進めない場合(真下に送る分)
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 3) % MOD
        else:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
    # i文字目でABCカウントを進める場合(右下に送る分)
    if S[i] == '?' or S[i] == 'A':
        dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % MOD
    if S[i] == '?' or S[i] == 'B':
        dp[i+1][2] = (dp[i+1][2] + dp[i][1]) % MOD
    if S[i] == '?' or S[i] == 'C':
        dp[i+1][3] = (dp[i+1][3] + dp[i][2]) % MOD

print(dp[len(S)][3])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
　　　https://www.hamayanhamayan.com/entry/2018/08/05/232127
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
・3べきの計算はpowの第三引数modで高速化
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3べきは使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i] + RQ[i], MOD)) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, LQ[i] + RQ[i] - 1, MOD)) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, LQ[i] + RQ[i] - 1, MOD)) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, LQ[i] + RQ[i] - 2, MOD)) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(ans)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3**LQ[i] * 3**RQ[i]は使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i]) * pow(3, RQ[i])) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, LQ[i]) * pow(3, RQ[i]-1)) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, LQ[i]-1) * pow(3, RQ[i])) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, LQ[i]-1) * pow(3, RQ[i]-1)) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3**LQ[i] * 3**RQ[i]は使わなかった?の分)
        case1 = A[i] * C[i] * pow(3, LQ[i]) * pow(3, RQ[i])
        # (A,B,?) と選ぶ場合
        case2 = A[i] * RQ[i] * pow(3, LQ[i]) * pow(3, RQ[i]-1)
        # (?,B,C) と選ぶ場合
        case3 = LQ[i] * C[i] * pow(3, LQ[i]-1) * pow(3, RQ[i])
        # (?,B,?) と選ぶ場合
        case4 = LQ[i] * RQ[i] * pow(3, LQ[i]-1) * pow(3, RQ[i]-1)
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3**LQ[i] * 3**RQ[i]は使わなかった?の分)
        case1 = A[i]* C[i] * 3**LQ[i] * 3**RQ[i]
        # (A,B,?) と選ぶ場合
        case2 = A[i] * RQ[i] * 3**LQ[i] * 3**(RQ[i]-1)
        # (?,B,C) と選ぶ場合
        case3 = LQ[i] * C[i] * 3**(LQ[i]-1) * 3**RQ[i]
        # (?,B,?) と選ぶ場合
        case4 = LQ[i] * RQ[i] * 3**(LQ[i]-1) * 3**(RQ[i]-1)
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
・別解
・Bの位置を決めて左右パターンを全部数え上げる。
"""

MOD = 10 ** 9 + 7
S = input()

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # kよりも左にあるAの個数
        a = S[:i].count('A')
        # kよりも左にある?の個数
        lq = S[:i].count('?')
        # kよりも右にあるCの個数
        c = S[i+1:].count('C')
        # kよりも右にある?の個数
        rq = S[i+1:].count('?')

        # (A,B,C) と選ぶ場合(後ろの3**lq * 3**rqは使わなかった?の分)
        case1 = a* c * 3**lq * 3**rq
        # (A,B,?) と選ぶ場合
        case2 = a * rq * 3**lq * 3**(rq-1)
        # (?,B,C) と選ぶ場合
        case3 = lq * c * 3**(lq-1) * 3**rq
        # (?,B,?) と選ぶ場合
        case4 = lq * rq * 3**(lq-1) * 3**(rq-1)

        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(int(ans))