H - Sugoroku Loop

2 secs 1024 MB

kusirakusira

問題

提出

テストケース

解説

便宜上マス目を 0-index で考え、以下マス目を $0, 1 \dots N-1$ とします。この問題は次のような DP で解くことができます。

$dp[i][j] = i$ ターン目にマス目 $j$ にたどり着ける通り数

初期値を $dp[0][0] = 1$ とし、ここから各マスへの遷移を考えていきます。移動できるのは $1 ～ 6$ マス、かつマス目は環状になっている為、 $dp[i][j]$ に対して、

$dp[i+1][(j+k)\bmod N] += dp[i][j](1 \le k \le 6)$

と遷移することができます。知りたかったのは $T$ ターン後にマス目 $0$ にいる通り数なので、 $dp[T][0]$ が答えになります。計算量は $O(TN)$ です。

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
using ll = long long;
​
int main()
{ 
    ll MOD9 = 998244353LL;
​
    ll N, T; cin >> N >> T;
    vector<vector<ll>> dp(T+1, vector<ll>(N,0));
    dp[0][0] = 1;
    for(int i = 1; i <= T; i++) {
        for(int j = 0; j < N; j++) {
            for(int k = 1; k <= 6; k++) { 
                dp[i][(j+k)%N] += dp[i-1][j];
                dp[i][(j+k)%N] %= MOD9;
            }
        }
    }
    cout << dp[T][0] << endl;
​
    return 0;
}

Python

xxxxxxxxxx
 
MOD = 998244353
N,T = map(int,input().split())
DP = [[0] * N for _ in range(T+1)]
DP[0][0] = 1
for i in range(0, T):
    for j in range(0, N):
        for k in range(1, 7):
            idx = (j + k) % N
            DP[i+1][idx] += DP[i][j]
            DP[i+1][idx] %= MOD
print(DP[T][0])
​