柱爷与远古法阵 题解
题意
(~~~~) 给出长 (L) 的走廊，每次等概率走 ([1,6]) 步，有 (n) 个传送门，第 (i) 个能进行 (u_i ightarrow v_i) 的传送，若每次步数走完后超过走廊则不行动，求走完的期望次数。
题解
(~~~~) 先往期望DP上想，不难想到设 (dp_i) 为当前在 (i) 位置走完的期望次数。
(~~~~) 若没有传送门，则
[Large dp_i=dfrac{sum_{j=1}^{6}dp_{i+j}}{6}+1
]
(~~~~) 若有传送门 (u ightarrow v) ，则
[Large dp_u=dp_v
]
(~~~~) 同时注意当 (i+j>L) 时，这步不能走，因此次数 (+1).
(~~~~) 化简一下，对于每一个位置 (i)：
[Large
left{egin{array}{l}
dp_i-sum_{j=1}^6 dp_{i+j}=6( ext{i没有传送门})\
dp_i=dp_{to_i}( ext{i有到}to_i ext{的传送门})
end{array}
ight.
]
(~~~~) 这样我们就得到了 (L) 个 (L) 元的方程组，用高斯消元求解即可。
(~~~~) 代码丑就不放了。qwq