[CF1349D]Slime and Biscuits

好长时间没打cf了,看了一下上一场cf的题感觉一道都做不出来了。我真的太菜了。
设$m=\sum_{i=1}^n a_i$
这个题暴力高斯消元的话变量很多,我们可以先想一想怎么减少变量。
首先考虑这么一个问题:计算终止状态只有第1个人获得所有饼干的期望步数。可以发现这个问题只和第1个人最初的饼干数有关。
设$g(i)$为第一个人手上饼干数为$i$,到第1个人第一次获得全部饼干的期望步数。那么有:
$$g(m)=0$$
$$g(i)=\frac{i}{m}g(i-1)+\frac{m-i}{m}(\frac{1}{n-1}g(i+1)+\frac{n-2}{n-1}g(i))+1\tag{0$\le$ i<m}$$
我们可以用这个式子提前预处理出所有的$g(i)$,时间复杂度$\Theta(m+n)$
放到原问题来看,这个相当于是一直取,直到第一次在这个位置终结的期望步数,那我们可以用这个减掉不合法的情况来得到第一次终结是在这个位置的概率和期望步数。
我们可以枚举不合法状态下第一次终结的位置,然后计算这个位置转过来的贡献。
设$t_i$为第一次终结在第i个人那里的期望步数,$p_i$为…的概率。

$$t_i=g(a_i)-\displaystyle\sum_{j\not =i}(t_j+g(0)p_j)$$
又可以知道$\displaystyle\sum_{i=1}^n p_i=1$
所以:
$$\displaystyle\sum_{i=1}^n t_i=g(a_i)-g(0)(1-p_i)$$
那么所有的$g(a_i)-g(0)(1-p_i)$全部相同,可以用类似方法把$p_i$给全部解出来。
最后答案就是所有$t_i$的和,直接利用之前式子求出来即可。
时间复杂度$\Theta(n+m)

Tagged with:

发表评论