柱爷与远古法阵 题解

题意

\(~~~~\) 给出长 \(L\) 的走廊，每次等概率走 \([1,6]\) 步，有 \(n\) 个传送门，第 \(i\) 个能进行 \(u_i \rightarrow v_i\) 的传送，若每次步数走完后超过走廊则不行动，求走完的期望次数。

---

题解

\(~~~~\) 先往期望DP上想，不难想到设 \(dp_i\) 为当前在 \(i\) 位置走完的期望次数。

\(~~~~\) 若没有传送门，则

\[\Large dp_i=\dfrac{\sum_{j=1}^{6}dp_{i+j}}{6}+1 \]

\(~~~~\) 若有传送门 \(u\rightarrow v\) ，则

\[\Large dp_u=dp_v \]

\(~~~~\) 同时注意当 \(i+j>L\) 时，这步不能走，因此次数 \(+1\).

\(~~~~\) 化简一下，对于每一个位置 \(i\)：

\[\Large \left\{\begin{array}{l} dp_i-\sum_{j=1}^6 dp_{i+j}=6(\text{i没有传送门})\\ dp_i=dp_{to_i}(\text{i有到}to_i\text{的传送门}) \end{array}\right. \]

\(~~~~\) 这样我们就得到了 \(L\) 个 \(L\) 元的方程组，用高斯消元求解即可。

\(~~~~\) 代码丑就不放了。qwq