Submission #31278042

---

Source Code Expand

MOD = 100000
w, h = map(int, input().split())
dp = [[[[0] * 2 for i in range(2)] for j in range(h)] for k in range(w)]
# dp[i][j][k][l] = 西から i 番目，南から j 番目の交差点に k の向き (0 = 東向き，1 = 北向き) で辿り着く場合の数
# ただし l = 1 の場合はこの交差点で向きを変えたことを表す
dp[0][0][0][0] = 1
dp[0][0][1][0] = 1
for i in range(w):
    for j in range(h):
        if i > 0:
            dp[i][j][0][0] = (dp[i - 1][j][0][0] + dp[i - 1][j][0][1]) % MOD
            dp[i][j][1][1] = dp[i - 1][j][0][0]
        if j > 0:
            dp[i][j][1][0] = (dp[i][j - 1][1][0] + dp[i][j - 1][1][1]) % MOD
            dp[i][j][0][1] = dp[i][j - 1][1][0]
print((dp[w - 1][h - 1][0][0] + dp[w - 1][h - 1][1][0]) % MOD)

Submission Info

Judge Result