問題
Lollipop Graph $L(m, n)$ は、クリーク $K_m$（完全グラフ）と path $P_n$（パスグラフ）をひとつの頂点でつないだグラフである。
- 頂点 $0, 1, \ldots, m-1$: クリーク部（全頂点対が辺で繋がっている）
- 頂点 $m-1, m, \ldots, m+n-1$: パス部（$m-1 \to m \to \cdots \to m+n-1$）
- 頂点 $m-1$: クリーク部とパス部の接続点
ランダムウォーク: 現在の頂点の隣接頂点のいずれか一様ランダムに移動する。
吸収状態: 頂点 $m+n-1$（パスの末端）に到達したら終了。
整数 $T$ と開始頂点 $s \in \{0, 1, \ldots, m+n-2\}$ が与えられる。ちょうど $T$ ステップ以内に吸収状態に到達する確率を $\bmod 10^9+7$ で出力せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $m$ | $2 \le m \le 10$ |
| $n$ | $1 \le n \le 10$ |
| $Q$ | $1 \le Q \le 10^5$ |
| $s$ | $0 \le s \le m+n-2$ |
| $T$ | $1 \le T \le 10^6$ |
| 出力 | 有理数を $\bmod 10^9+7$ で |
入出力例
入力例 1
3 2 3
0 5
2 3
3 10出力例 1
（計算結果を mod 10^9+7 で出力）$L(3,2)$: クリーク $K_3$（頂点0,1,2）+ パス（頂点2→3→4）。吸収状態 = 頂点4。
概念図: Lollipop Graph $L(3, 2)$
ヒント（段階的開示）
ヒント1: 方向性
クリーク内の非接続点頂点は対称なので、状態を「クリーク内非接続点（代表）」「クリーク接続点（$m-1$）」「パス上の各頂点」に分けて遷移行列を構築する。吸収状態に自己ループを付けると、$A^T$ の $(s, \text{吸収})$ 成分が累積確率になる。
ヒント2: アプローチ
遷移確率は有理数（例: $1/(m-1)$）なので $\bmod 10^9+7$ 上の逆元で表現する。$T \le 10^6$ に対してダブリング（$A^{2^k}$ を $k = 0 \ldots 19$ まで事前計算）すれば、各クエリを $O(S^3 \cdot 20)$ で処理できる。$S = m+n \le 20$。
ヒント3: コード骨格
# 行列累乗
def mat_mul(A, B, mod=10**9+7):
n = len(A)
C = [[0]*n for _ in range(n)]
for i in range(n):
for k in range(n):
if A[i][k] == 0: continue
for j in range(n):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
return C
# ダブリング事前計算
LOG = 20
pw = [None] * LOG
pw[0] = A # 遷移行列
for k in range(1, LOG):
pw[k] = mat_mul(pw[k-1], pw[k-1])
# クエリ処理
def query(s, T):
R = 単位行列
for k in range(LOG):
if T & (1 << k):
R = mat_mul(R, pw[k])
return R[s][absorbed_state]模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def modinv(a, m=MOD):
return pow(a, m-2, m)
def mat_mul(A, B):
n = len(A)
C = [[0]*n for _ in range(n)]
for i in range(n):
for k in range(n):
if A[i][k] == 0: continue
for j in range(n):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
return C
def solve():
m, n, Q = map(int, input().split())
S = m + n # 状態数（吸収含む）
A = [[0]*S for _ in range(S)]
# クリーク内非接続点 i (0 <= i <= m-2)
inv_dc = modinv(m - 1)
for i in range(m-1):
for j in range(m-1):
if i != j:
A[i][j] = inv_dc
A[i][m-1] = inv_dc
# 接続点 m-1: 次数 = m
inv_conn = modinv(m)
for i in range(m-1):
A[m-1][i] = inv_conn
if n >= 1:
A[m-1][m] = inv_conn
else:
A[m-1][S-1] = inv_conn
# パス頂点 m
if n >= 1:
inv2 = modinv(2)
A[m][m-1] = inv2
if n == 1:
A[m][S-1] = inv2
else:
A[m][m+1] = inv2
# パス頂点 m+1 .. m+n-2
inv2 = modinv(2)
for v in range(m+1, m+n-1):
A[v][v-1] = inv2
if v == m+n-2:
A[v][S-1] = inv2
else:
A[v][v+1] = inv2
# 吸収状態に自己ループ
A[S-1][S-1] = 1
# ダブリング
LOG = 20
pw = [None] * LOG
pw[0] = A
for k in range(1, LOG):
pw[k] = mat_mul(pw[k-1], pw[k-1])
results = []
for _ in range(Q):
s, T = map(int, input().split())
R = [[int(i==j) for j in range(S)] for i in range(S)]
t = T
for k in range(LOG):
if t & 1:
R = mat_mul(R, pw[k])
t >>= 1
results.append(R[s][S-1])
print('\n'.join(map(str, results)))
solve()
Step-by-Step 解説
1Lollipop Graph の特性
$L(m, n)$ はランダムウォークの「混合時間」が $\Theta(mn^2)$ になるグラフとして知られる。クリーク部でランダムウォークが均一化し、パス部で時間がかかる。
$L(m, n)$ はランダムウォークの「混合時間」が $\Theta(mn^2)$ になるグラフとして知られる。クリーク部でランダムウォークが均一化し、パス部で時間がかかる。
2有理数の mod p 表現
遷移確率は $1/(m-1)$ や $1/m$ などの有理数。$\bmod 10^9+7$ 上でフェルマーの小定理により $a^{-1} \equiv a^{p-2} \pmod p$ で逆元を計算する。
遷移確率は $1/(m-1)$ や $1/m$ などの有理数。$\bmod 10^9+7$ 上でフェルマーの小定理により $a^{-1} \equiv a^{p-2} \pmod p$ で逆元を計算する。
3吸収状態の自己ループ
吸収状態に $A[\text{abs}][\text{abs}] = 1$ を設定することで、$A^T$ の $(s, \text{abs})$ 成分が「$T$ ステップ以内に到達する累積確率」になる。
吸収状態に $A[\text{abs}][\text{abs}] = 1$ を設定することで、$A^T$ の $(s, \text{abs})$ 成分が「$T$ ステップ以内に到達する累積確率」になる。
4ダブリングによる $A^T$ の計算
$T$ のビット表現を利用し、$A^T = A^{2^{k_1}} \cdot A^{2^{k_2}} \cdots$。$\log_2(10^6) \approx 20$ ビットで十分。
$T$ のビット表現を利用し、$A^T = A^{2^{k_1}} \cdot A^{2^{k_2}} \cdots$。$\log_2(10^6) \approx 20$ ビットで十分。
計算量
前処理（ダブリング）: $O(S^3 \log T)$ — $S = m+n \le 20$, $\log T \le 20$
各クエリ: $O(S^3 \log T)$ — 最悪 $8000 \times 20 = 160000$ 演算
全体: $O((1 + Q) \cdot S^3 \log T)$ — $Q = 10^5$ のとき約 $1.6 \times 10^{10}$（遅い！）
最適化: クエリをオフラインでソートし、同じ $T$ はキャッシュする
各クエリ: $O(S^3 \log T)$ — 最悪 $8000 \times 20 = 160000$ 演算
全体: $O((1 + Q) \cdot S^3 \log T)$ — $Q = 10^5$ のとき約 $1.6 \times 10^{10}$（遅い！）
最適化: クエリをオフラインでソートし、同じ $T$ はキャッシュする
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 吸収状態に自己ループなし | 累積確率でなく到達確率になる | A[S-1][S-1] = 1 |
| 接続点の次数を $m-1$ にする | クリーク内 $m-1$ + パス方向 $1$ = $m$ | deg_conn = m |
| 逆元計算を忘れる | 整数除算は mod 上で不可 | modinv(deg) |
| ダブリングの順序ミス | t &= 1 確認前に t >>= 1 | if t & 1 → t >>= 1 |
次のステップ
- 発展問題: Random walk on expander graph の混合時間をスペクトルギャップから求める
- 関連: 電気抵抗ネットワークと有効抵抗 → Cover Time の上界（$O(m \cdot \text{resistance})$）
- 応用: マルコフ連鎖の定常分布計算（左固有ベクトル）