[JSOI2009]有趣的游戏
其实是专题里硬币游戏的弱化版
考虑trie树建出来，然后做AC自动机
转移方程比较容易，发现是环状的，所以需要高斯消元
然后发现高斯消元不会写了233……
注意：(huge{AC自动机用高斯消元要注意根节点0的考虑})
[SDOI2017]硬币游戏
为[JSOI2009]有趣的游戏 的加强版
如果直接高消，复杂度为(O((nm)^3))，只能拿到40分
细想了一下得到优化的过程
按照有趣的游戏的想法高消复杂度是(O((nm)^3))的，这是因为考虑的节点太多了
实际上，为了得到每个人获胜的概率，我们只关心AC自动机上终止节点的答案
所以应该想办法列出终止节点之间互相转移的方程
这里发现上次想的思路似乎是错的了
应该是假如(A)串长度(k)的前缀和(B)串长度为(k)的后缀相同，那么我想构造出(A)串，在构造出前(k)个以后，是有几率直接就完成了(B)串的
而这个几率是(frac{1}{2^{m-k}})，就是说B串的前(m-k)个已经构造好了
这个时候就达到了想有(A)但意外得到了(B)的效果
推广一下，对于每一个串(A)，都有可能意外得到串(B)，我们可以认为串(B)的概率就是所有 串(A)概率×串(A)到串(B)概率 的贡献之和。（特别的，当(A=B)时，串(A)到串(B)概率为(1)）
特殊的，考虑根节点即空串
又有所有终止节点的概率和为(1)
就得到了(n+1)个方程，复杂度即为(O(n^3))
XOR和路径
位运算位之间无影响，故按位考虑，答案即为每一位为(1)的期望与这一位价值的乘积之和
对于每一个点(i)和点(j)，若之间有权的当前位为(w)的边，则有(f[i]=frac{1}{deg[i]}(sum_{w=0} f[j]+sum_{w=1}(1-f[j])))
化简得(deg[i]*f[i]-sum_{w=0}f[j]+sum_{w=1}f[j]=sum_{w=1})
用高斯消元求解即可
[NOI2005]聪聪与可可
用(spfa)预处理出每两个点之间的最短路
然后就可以dfs模拟聪聪走的两步
两步分开模拟，如果发现抓到了就返回(1)
如果还没抓到就枚举可可走的，算期望，再加1
OSU! & Easy
OSU!
考虑怎么维护这个(x^3)的期望
发现转移时((x+1)^3=x^3+3x^2+3x+1)
那么要得到((x+1)^3)的期望我们只需知道(x^3)，(x^2)，(x)的期望分别是多少
维护(x^2)的期望时同理，可用(x)期望得出
每次先更新(x^3)的期望，然后(x^2)，最后(x)，可以省空间。
Easy
同一个逻辑（(hw)语气），这次只用维护(x^2)了
如果为o就转移，为x就清空，?的话就是(frac{1}{2})的概率转移，就是转移的时候乘(frac{1}{2})
单选错位
设第(k)道题有(a)个选项，第(k+1)道题有(b)个选项
则第(k+1)道正确概率为(frac{1}{min (a,b)})
算，就硬算
分手是祝愿
有一些键是必须要按的，可以从大到小扫一遍，得到最少操作次数(cnt)
如果(cntleq k)，则答案为(cnt)乘上个阶乘
否则考虑随机的情况
设(f[i])为从剩(i)个转移到(i-1)个要按的期望次数
则(f[i]=frac{i}{n}+frac{n-i}{n}(f[i+1]+1+f[i]))
其中(frac{i}{n})为按对了的贡献，如果按错了，就得重新做一遍(f[i+1]
ightarrow f[i])，再做(f[i])
整理得(f[i]=frac{n+(n-i)f[i+1]}{i})
(f[n+1]=0)，倒序即可
[SHOI2014]概率充电器
求有电元件数的期望也就是所有元件有电概率之和
考虑有电是一个或运算，我们反过来，考虑每一个元件没电的概率，这是可以根据乘法原理维护的
则有转移方程：(f[u]=sumlimits_{(u,v)in E}(1-p(u,v)+p(u,v)*f[v]))
这个数据范围高斯消元就算了（为什么有这个标签啊），直接(dfs)，换根一下就行
博物馆
需要求的是在每个房间相遇的概率
刚开始想到的是高消算出P,V在每个点的期望再挨个点算
然后发现这就和初始位置没关系了
转移肯定是环状的，那么高斯消元得用，就需要考虑一下状态的定义
发现n的范围很小，只有20，同时他们相遇以后就不再走，那么所有相遇情况的期望加起来就是1，且每种情况出现次数只有1，也就是说，所有相遇情况的概率就是这种情况的期望值
可以得出转移方程，分四种情况（都不动，V动，P动，都动），并注意一些防止相遇过的限制条件
那么就可以用高消算出P,V在每一个位置的期望值f[i][j]
即最终答案在i相遇的概率为f[i][i]
共有n2个方程，复杂度为O((n2)3)=O(n6)