题解：
什么鬼啊。。。
网上的都是直接暴力状压
那么复杂度是2^n*n的
那么n=30,m=0直接被卡掉了吧
首先先缩点这是很显然的
然后问题就变成了遍历这张图完全图的期望时间
f[s]=(1+f[s])*p[]+sigma(f[s']*p[])
这个是个比较普通的期望dp方程
我觉得有一种优化的方法是
map存vector的时候，可以存每个数值大小的数有几个
这样复杂度应该是比较靠谱的。。。
但是我并不太会严格证明
代码：
题解：
什么鬼啊。。。
网上的都是直接暴力状压
那么复杂度是2^n*n的
那么n=30,m=0直接被卡掉了吧
首先先缩点这是很显然的
然后问题就变成了遍历这张图完全图的期望时间
f[s]=(1+f[s])*p[]+sigma(f[s']*p[])
这个是个比较普通的期望dp方程
我觉得有一种优化的方法是
map存vector的时候，可以存每个数值大小的数有几个
这样复杂度应该是比较靠谱的。。。
但是我并不太会严格证明
代码：