Submission #31263127

---

Source Code Expand

MOD = 10000
n, k = map(int, input().split())
decided = [-1] * n
for i in range(k):
    a, b = map(int, input().split())
    decided[a - 1] = b - 1
dp = [[[0] * 3 for i in range(3)] for j in range(n)]
# dp[i][j][k] = i - 1 日目にパスタ j，i 日目にパスタ k を食べた場合の，i 日目までのパスタの食べ方の場合の数
if decided[0] != -1:
    if decided[1] != -1:
        dp[1][decided[0]][decided[1]] = 1
    else:
        for j in range(3):
            dp[1][decided[0]][j] = 1
else:
    if decided[1] != -1:
        for i in range(3):
            dp[1][i][decided[1]] = 1
    else:
        for i in range(3):
            for j in range(3):
                dp[1][i][j] = 1
for i in range(2, n):
    for j in range(3):
        for k in range(3):
            if decided[i] != -1 and decided[i] != k:
                continue # 決定済みの予定と食い違うものは除外
            for l in range(3):
                if l == j == k:
                    continue # 同じパスタを 3 日連続食べるケースを除外
                dp[i][j][k] += dp[i - 1][l][j]
                dp[i][j][k] %= MOD
answer = 0
for i in range(3):
    for j in range(3):
        answer += dp[n - 1][i][j]
answer %= MOD
print(answer)

Submission Info

Judge Result