ABC275E - Sugoroku 4

考え方

modの逆数（modの逆数 - 競プロはじめました）さえわかれば，普通のDP．

回答例

dはゴールまでの距離．
nxt(次の位置) = move(今いる位置，出目)
dp[i回目に][位置jにいる] 確率．

N, M, K = map(int, input().split())
mod = 998244353
invM = pow(M, mod - 2, mod)

d = [N - i for i in range(N + 1)]

def move(pos, val):
    if val <= d[pos]:
        return pos + val
    return N - (val - d[pos])

dp = [[0] * (N + 1) for _ in range(K + 1)]
dp[0][0] = 1
for i in range(K):
    for pos in range(N):
        for val in range(1, M + 1):
            nxt = move(pos, val)
            dp[i + 1][nxt] += dp[i][pos] * invM
            dp[i + 1][nxt] %= mod

ans = 0
for i in range(K + 1):
    ans += dp[i][N]
    ans %= mod
print(ans)