E - Sugoroku 4

[hxrxchang]

https://atcoder.jp/contests/abc275/tasks/abc275_e

問題概要

0からN(Nは最大1000)までの番号がついたマスがある双六がある。最初は0にいる。 ルーレットは1~M(Mは最大10)の数字がでるルーレットを回して、出た数だけ進める。 ルーレットをK回まで回すとき、ゴールできる確率を求めよ。

解き方

先週もやった確率DP。 dp[i][j]: ルーレットをk回まわして、マスjにつく確率を更新していく。

func solve() {
    in := getInts()
    n, m, k := in[0], in[1], in[2]

    dp := make([][]int, k + 1)
    for i := 0; i <= k; i++ {
        dp[i] = make([]int, n + 1)
    }
    dp[0][0] = 1

    inv := modPow(m, MOD - 2, MOD)

    for i := 0; i < k; i++ {
        for j := 0; j < n; j++ {
            for l := 1; l <= m; l++ {
                next := j + l
                if next > n {
                    next = n - (next - n)
                }
                dp[i + 1][next] += dp[i][j] * inv
                dp[i + 1][next] %= MOD
            }
        }
    }

    ans := 0
    for i := 0; i <= k; i++ {
        ans += dp[i][n]
        ans %= MOD
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc275/submissions/55167888