問題
$N$ 頂点の有向グラフ（頂点 $1$〜$N$）で確率的に遷移する。頂点 $N$ は吸収状態。各非吸収頂点 $v$ について：
- 頂点 $1$ から出発して頂点 $N$ に吸収されるまでのステップ数の期待値 $E[v]$
- 同ステップ数の分散 $\text{Var}[v]$
答えは mod $998244353$ で出力せよ。
制約
$2 \le N \le 500$
$1 \le M \le N^2$
遷移確率は有理数 $p/q$
時間制限: 2sec / メモリ: 256MB
入出力例
入力例 1
3 4
1 2 1/2
1 3 1/2
2 1 1/2
2 3 1/2出力例 1
3 5$E[1]=3$: 頂点1から3への期待ステップ数。$\text{Var}[1]=E[T^2]-E[T]^2=14-9=5$。
概念図: 吸収マルコフ連鎖の方程式
ヒント（段階的開示）
ヒント1: 期待値の連立方程式
$E[T][v] = 1 + \sum_{u \ne N} p_{v,u} E[T][u]$（$E[T][N] = 0$）。非吸収頂点のみの $(I-P)\mathbf{E} = \mathbf{1}$ をガウス消去法（mod p）で解く。
ヒント2: 分散の計算方法
$E[T^2][v]$ の方程式: $E[T^2][v] = 2E[T][v] - 1 + \sum_u p_{v,u} E[T^2][u]$
係数行列は $E[T]$ と同じ $(I-P)$、右辺のみ変えて再び解く。
$\text{Var}[v] = E[T^2][v] - (E[T][v])^2$。
係数行列は $E[T]$ と同じ $(I-P)$、右辺のみ変えて再び解く。
$\text{Var}[v] = E[T^2][v] - (E[T][v])^2$。
ヒント3: ガウス消去法 mod p
def gaussian_elimination(A, b, n, MOD):
mat = [A[i][:] + [b[i]] for i in range(n)]
for col in range(n):
# pivot を見つける
pivot = next((r for r in range(col, n) if mat[r][col] != 0), -1)
mat[col], mat[pivot] = mat[pivot], mat[col]
inv = pow(mat[col][col], MOD - 2, MOD)
for j in range(col, n + 1):
mat[col][j] = mat[col][j] * inv % MOD
for row in range(n):
if row == col: continue
f = mat[row][col]
for j in range(col, n + 1):
mat[row][j] = (mat[row][j] - f * mat[col][j]) % MOD
return [mat[i][n] for i in range(n)]模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 998244353
def modinv(a, m=MOD):
return pow(a, m - 2, m)
def gaussian_elimination(A, b, n):
mat = [A[i][:] + [b[i]] for i in range(n)]
for col in range(n):
pivot = -1
for row in range(col, n):
if mat[row][col] != 0:
pivot = row
break
if pivot == -1:
return None
mat[col], mat[pivot] = mat[pivot], mat[col]
inv = modinv(mat[col][col])
for j in range(col, n + 1):
mat[col][j] = mat[col][j] * inv % MOD
for row in range(n):
if row == col:
continue
f = mat[row][col]
if f == 0:
continue
for j in range(col, n + 1):
mat[row][j] = (mat[row][j] - f * mat[col][j]) % MOD
return [mat[i][n] for i in range(n)]
def solve():
N, M = map(int, input().split())
P = [[0] * N for _ in range(N)]
for _ in range(M):
parts = input().split()
u, v = int(parts[0]) - 1, int(parts[1]) - 1
p, q = map(int, parts[2].split('/'))
prob = p * modinv(q) % MOD
P[u][v] = (P[u][v] + prob) % MOD
abs_state = N - 1
non_abs = [v for v in range(N) if v != abs_state]
n = len(non_abs)
idx = {v: i for i, v in enumerate(non_abs)}
# (I - P_sub) * E = 1
A = [[0] * n for _ in range(n)]
b = [1] * n
for i, v in enumerate(non_abs):
A[i][i] = 1
for u in range(N):
prob = P[v][u]
if prob == 0 or u == abs_state:
continue
j = idx[u]
A[i][j] = (A[i][j] - prob) % MOD
E = gaussian_elimination(A, b, n)
# (I - P_sub) * E2 = 2E - 1
b2 = [(2 * E[i] - 1) % MOD for i in range(n)]
E2 = gaussian_elimination(A, b2, n)
i0 = idx[0] # 頂点 1 (0-indexed: 0)
e_val = E[i0]
var_val = (E2[i0] - e_val * e_val) % MOD
print(e_val, var_val)
solve()
Step-by-Step 解説
1期待値の方程式
$E[T][v] = 1 + \sum_u p_{v,u} E[T][u]$ を整理して $(I-P_{\text{sub}})\mathbf{E} = \mathbf{1}$。吸収状態は $E=0$ なので除外。
$E[T][v] = 1 + \sum_u p_{v,u} E[T][u]$ を整理して $(I-P_{\text{sub}})\mathbf{E} = \mathbf{1}$。吸収状態は $E=0$ なので除外。
2ガウス消去法 mod p
浮動小数点を使わず、モジュラー逆元 $a^{-1} \equiv a^{p-2} \pmod{p}$ でピボット行を正規化。$O(N^3)$。
浮動小数点を使わず、モジュラー逆元 $a^{-1} \equiv a^{p-2} \pmod{p}$ でピボット行を正規化。$O(N^3)$。
32次モーメントの方程式
$E[T^2][v] = 2E[T][v] - 1 + \sum_u p_{v,u} E[T^2][u]$。係数行列は同じ $(I-P_{\text{sub}})$、右辺のみ $2E-1$ に変えて再計算。
$E[T^2][v] = 2E[T][v] - 1 + \sum_u p_{v,u} E[T^2][u]$。係数行列は同じ $(I-P_{\text{sub}})$、右辺のみ $2E-1$ に変えて再計算。
4分散の計算
$\text{Var}[v] = E[T^2][v] - (E[T][v])^2$。mod 演算で負の値になる可能性があるため `% MOD` を忘れずに。
$\text{Var}[v] = E[T^2][v] - (E[T][v])^2$。mod 演算で負の値になる可能性があるため `% MOD` を忘れずに。
5有理数の変換
入力の $p/q$ を $p \cdot q^{-1} \pmod{998244353}$ に変換。Fermat の小定理で $q^{998244351}$ を計算。
入力の $p/q$ を $p \cdot q^{-1} \pmod{998244353}$ に変換。Fermat の小定理で $q^{998244351}$ を計算。
計算量
ガウス消去法: $O(N^3)$（2回実行）
遷移行列の構築: $O(M)$
合計: $O(N^3)$ — $N \le 500$ で約 $1.25 \times 10^8$ 演算
遷移行列の構築: $O(M)$
合計: $O(N^3)$ — $N \le 500$ で約 $1.25 \times 10^8$ 演算
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 吸収状態を方程式に含める | $E[N]=0$ は自明なので不要 | 非吸収頂点のみを行列に含める |
| 分散が負になる | mod で負の値を正規化忘れ | (E2[i] - e_val*e_val) % MOD |
| 有理数を float で扱う | 精度誤差で WA | 必ず mod 演算に変換してから処理 |
| 係数行列を 2 回再構築 | 非効率 | $A$ は同じなので b2 のみ変えて再利用 |
次のステップ
- 発展: 複数の吸収状態 → 各吸収状態への到達確率 + 条件付き期待値
- 応用: ランダムウォークの期待値 → Dirichlet 問題との対応
- 類題: グラフ上のランダムウォークで特定頂点を訪問する期待時間