题目概述

本题要求计算在骰子旅行过程中，键盘手 $S$ 的废话指数的期望值。废话指数定义为：每当访问到一个之前访问过的地点时，记录下上一次从该地点掷骰子前往的地点编号，并将所有记录的值求和。

算法思路

核心观察

废话指数的产生条件是：当第 $t$ 次访问地点 $i$ 时，如果之前已经在时间 $t'$ 访问过 $i$，则记录 $s_{t'+1}$。

这等价于：对于每个地点 $i$，考虑所有第二次及以后访问该地点的时间 $t$，记录第一次访问 $i$ 后前往的地点 $s_{t'+1}$。

状态设计与DP方程

本解法采用了动态规划方法，分别维护三个关键状态：

1. 基础概率状态

$f[j][k]$：表示经过 $j$ 步后到达地点 $k$ 的概率

状态转移：

$$f[j][l] = \sum_{k \to l} \frac{1}{cnt[k]} \cdot f[j-1][k] $$

2. 贡献状态

$g[j][l]$：表示经过 $j$ 步到达 $l$，且最后一次访问关键地点 $i$ 后产生的期望贡献

状态转移：

• 如果 $k = i$（关键地点）：$g[j][l] += \frac{1}{cnt[k]} \cdot f[j-1][k] \cdot l$
• 否则：$g[j][l] += \frac{1}{cnt[k]} \cdot g[j-1][k]$

3. 答案状态

$ans[j][l]$：表示经过 $j$ 步到达 $l$ 时，所有历史贡献的累积期望

状态转移：

$$ans[j][l] = \sum_{k \to l} \frac{1}{cnt[k]} \cdot ans[j-1][k] $$

当 $l = i$ 时额外加上：$ans[j][i] += g[j][i]$

算法流程

for 每个关键地点 i (1 ≤ i ≤ n):
    初始化 f[0][s] = 1
    
    for 步数 j from 1 to T:
        for 每个地点 k (1 ≤ k ≤ n):
            for 每个后继地点 l in to[k]:
                // 更新概率
                f[j][l] += f[j-1][k] * inv[cnt[k]]
                // 更新答案累积
                ans[j][l] += ans[j-1][k] * inv[cnt[k]]
                // 更新贡献
                if k == i:
                    g[j][l] += f[j-1][k] * inv[cnt[k]] * l
                else:
                    g[j][l] += g[j-1][k] * inv[cnt[k]]
        
        // 在关键地点记录贡献
        ans[j][i] += g[j][i]
    
    // 累加最终答案
    res += ans[T][1..n]

算法正确性证明

贡献计算正确性

对于每个关键地点 $i$：

• $f[j][k]$ 准确记录了到达各点的概率
• $g[j][l]$ 在第一次访问 $i$ 后开始记录贡献，准确反映了"上一次从 $i$ 前往的地点"的期望值
• $ans[j][l]$ 累积了所有时间步的贡献，确保每个重复访问都被正确计数

模运算处理

由于需要输出模 $998244353$ 意义下的结果，算法中：

• 使用模逆元代替除法：$inv[i]$ 预处理
• 所有运算在模意义下进行
• 最终结果满足 $res \equiv \frac{p}{q} \pmod{998244353}$

复杂度分析

时间复杂度

• 外层循环：$O(n)$
• 步数循环：$O(T)$
• 地点循环：$O(n)$
• 边遍历：$O(\sum m_i) \leq O(5000)$

总复杂度：$O(n \cdot T \cdot \sum m_i) \approx 100 \times 100 \times 5000 = 5 \times 10^7$，可接受。

空间复杂度

• 状态数组：$O(n \cdot T)$
• 邻接表：$O(\sum m_i)$

样例解析

样例1：n=5, s=1, T=2

关键路径：1 → {2,3,4} → 1

贡献分析：

• 访问2后返回1：概率1/6，贡献2
• 访问3后返回1：概率1/6，贡献3
• 访问4后返回1：概率1/6，贡献4

期望：$\frac{1}{6}(2+3+4) = \frac{3}{2}$

模运算：$2 \times 499122178 \equiv 3 \pmod{998244353}$

总结

算法亮点

1. 分离关注点：将概率、贡献、答案分别维护，逻辑清晰
2. 高效状态转移：利用图的稀疏性，只遍历实际存在的边
3. 模运算处理：正确使用模逆元处理概率计算

核心思想

通过枚举关键地点 + 动态规划，准确计算每个地点作为重复访问点时产生的期望贡献，最终求和得到总期望。

该解法充分利用了数据范围特点，通过精细的状态设计实现了高效计算，是概率DP的典型应用。