LOJ6509 雅礼集训 2018 Day7 C DP线性消元

「雅礼集训 2018 Day7」C 考虑一个乱走的过程，可以发现在某个点，除了最后一步（停止），每一步的期望长度都是所在的点到所有点距离的平均数。 那么考虑记录每个点走了多少次。热动分析一下发现所有同色点的期望次数都是一样的。 那么搞一个DP，令$f_{i,0/1}$表示有$i$个$1$，$0/1$期望走多少次（对于一个点）。这个DP是倒序的，也就是令全是某个数为边界倒推。 $$f_{i,0} = \frac{i}{n} f_{i-1,0} + \frac{n-i-1}{n} f_{i+1,0} + \frac{1}{n} f_{i+1,1} + \frac{1}{n}$$ $$f_{i,1}= \frac{i-1}{n} f_{i-1,1} + \frac{1}{n} f_{i-1,0} + \frac{n-i}{n} f_{i+1,1} + \frac{1}{n}$$ 这个式子的意思是这样的：以第一个为例，有一定概率走到$1$，那么无贡献，继承即可。有一定概率走到$0$，继承其它点，并加上走到的那个点的贡献。 注意一个边界问题：因为考虑的是非最后一次，当只剩下一个点并翻转它的时候，不能加$\frac{1}{n}$。 移项之后可以由$i-1,i$推出$i+1$。注意到当$i=0,i=n$时，期望次数是$0$。那么直接设每一项是$xf_{1,0}+yf_{1,1}+z$，推到边界，解出即可。