首先我们有一个很\(naive\)的想法是构建出转移矩阵，然后矩阵快速幂迭代足够多次，得到的结果约为答案
复杂度\(O((nl)^3logk)\),正确性玄学
但是我们肯定不是要介绍这种方法，而是另外一种
我们设\(x_i\)为整局游戏经过\(x\)点的期望次数，则初始时\(x_0=1\)，\(p_{i,j}\)为\(i\)转移到\(j\)的概率，则有
\[x_0=1+p_{0,0}x_0+p_{1,0}x_1……+p_{n-1,0}x_{n-1}\]
\[x_i=p_{0,i}x_0+p_{1,i}x_1……+p_{n-1,i}x_{n-1}(i≠0)\]
把未知项移到一侧
\[-x_0+p_{0,0}x_0+p_{1,0}x_1……+p_{n-1,0}x_{n-1}=-1\]
\[-x_i+p_{0,i}x_0+p_{1,i}x_1……+p_{n-1,i}x_{n-1}=0(i≠0)\]
由于题目要求移动到某个标记节点就停止，所以标记节点处的期望次数就是它所对应的概率
所以直接高斯消元就可以得到答案，至于转移矩阵用AC自动机跑个trie图出来就好了
原文：https://www.cnblogs.com/knife-rose/p/12028078.html