Atcoder Regular Contest 081のD問題をPythonで書いてみた
Xパターン(縦2×横1)が3通り
Yパターン(縦1×横2)が6通り
上が一番左における(配列0番目)、それぞれの場合の数。
次に、
Xの色を固定した場合、Xー>Xは2パターン。X->Yも2パターン。
Yの色を固定した場合、Y->Xは1パターン。Y→Yは3パターン。
あとはこれをコードに落とし込むだけ。
INF = 10**9+7
# n = int(input())
# s1 = list(input())
# s2 = list(input())
def calc_patterns_tnk(n, s1, s2):
if len(s1) != len(s2):
print("error!")
way = 1
pattern = 0
i = 0
while i <= n-1:
if s1[i] == s2[i]:
i += 1
way *= (3 - pattern)
pattern = 1
else:
i += 2
if pattern == 1:
way *= 2
elif pattern == 2:
way *= 3
else:
way *= 6
pattern = 2
return way % INF
print(calc_patterns_tnk(3, 'aab', 'ccb')) # -> 6
print(calc_patterns_tnk(1, 'Z', 'Z')) # -> 3
print(calc_patterns_tnk(52, 'RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn', 'RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn')) # -> 958681902