有三个骰子，分别有\(k_1,k_2,k_3\)面，每次同时投掷得\(x_1,x_2,x_3\)，分数增加\(x_1+x_2+x_3\)，若三者的值分别为\(a,b,c\)，则分数清零，若分数大于\(n\)，则结束操作。求期望多少次投掷后结束操作（zoj-3329）
尝试用上一题的做法来解，设\(f_i\)表示当前分数为\(i\)时的期望还要进行多少次，令\(p_k\)表示三个骰子分数和为\(k\)的概率
则可以列出方程：\(f_i=\sum_kp_k(f_{i+k}+1)\)
将\(1\)提出来，把\(p_0\)单独提出来，得到\(f_i=1+f_0p_0+\sum_{k\not =0}p_kf_{i+k}\)
舍弃之前说的高斯消元做法，介绍一种更优秀的做法
由于所有式子都要用到\(p_0\)，所以不妨假设\(f_i=a_ip_0+b_i\)
然后将\(f_{i+k}=a_{i+k}p_0+b_{i+k}\)套到之前的式子里去，得到
\(f_i=1+f_0p_0+\sum_{k\not =0}p_k(a_{i+k}f_0+b_{i+k})\\=(p_0+\sum_{k\not =0}p_ka_{i+k})f_0+\sum_{k\not =0}p_kb_{i+k}+1\)
对比式子：\(f_i=a_ip_0+b_i\)，发现两个式子结构相同，可得：
\(a_i=p_0+\sum_{k\not =0}p_ka_{i+k}\\b_i=1+\sum_{k\not =0}p_kb_{i+k}\)
由于\(a_i,b_i=0(i>n)\)，而上面的式子中所有量是可以递推而得，没有循环转移关系的，所以可以递推得到\(a_0,b_0\)
将\(i=0\)代入，得到\(f_0=a_0f_0+b_0\)，即\(f_0=\frac {b_0}{1-a_0}\)，得解
树上情况一棵 \(n\) 个结点的树，从点 \(x\) 出发，每次等概率随机选择一条与所在点相邻的边走过去。\(Q\) 次询问，每次询问给定一个集合 \(S\)，求如果从 \(x\) 出发一直随机游走，直到点集 \(S\) 中所有点都至少经过一次的话，期望游走几步。（pkuwc2018随机游走）
这题之前就写过题解，在这，可以看看中间如何将树上情况的循环转移优化成递推
基本思路也是设每个节点从父亲转移，递推求得系数\(a_i,b_i\)，这样是\(O(n)\)的
分层图情况&一般图情况这个待填坑吧，分层图好像可以玩，听说去年pkuwc上有人想出了一个在一般图上高斯消元的高效算法