D - Poor Sense of Direction

2 secs 1024 MB

loop0919

問題

提出

テストケース

解説

$\mathrm{dp}[i][j]$ を、 $i$ 分時点で街 $j$ にいる確率と定義した動的計画法で解くことが出来ます。

遷移時に $k$ の逆元 $(1 \leq k \leq N)$ を求める必要がありますが、低速な言語だと毎回計算していると間に合わないため、前計算をしておく必要があります。

前計算を行った場合、動的計画法の状態数が $O(NT)$ 、遷移回数の合計は $O(MT)$ ですので、計算量は $O((N+M)T + N\log \mathrm{mod})$ や $O((N+M)T)$ で求めることができます。
(ここで $\mathrm{mod} = 998244353$ とします。)

想定解

pypy3

xxxxxxxxxx
 
MOD = 998244353
​
N, M, T = map(int, input().split())
​
# Xの逆元を求める
inv_list = [-1] * (N+1)
def inv(X):
    if inv_list[X] != -1: return inv_list[X]
    inv_list[X] = pow(X, MOD-2, MOD)
    return inv_list[X]
​
outdegrees = [0]*N
edges = []
​
for _ in range(M):
    u, v, t = map(int, input().split())
    u -= 1; v -= 1
    
    outdegrees[u] += 1
    outdegrees[v] += 1
    
    edges.append((u, v, t))
    edges.append((v, u, t))
​
dp = [[0]*N for _ in range(T+1)]
​
dp[0][0] = 1
​
for i in range(1, T+1):
    for u, v, t in edges:
            # 街N から来る経路は無視
            if v == N-1:
                continue
            if i - t >= 0:
                p = dp[i - t][v]
                dp[i][u] += (p * inv(outdegrees[v]))
                dp[i][u] %= MOD
​
print(sum([d[N-1] for d in dp]) % MOD)