分析：

我们从比较简单的情况开始考虑。

假设只有两个数 0 和 1

那么当前的状态可以由 0 的个数唯一确定

设 f[i] 表示当前有 i 个 0 的时候变到所有数都一样的期望步数，那么边界为 f[0]=0， f[n]=0.

注意进行一次操作后， 0 的数目不一定发生变化.

假如现在有 i 个 0 ，那么一共有 n∗(n−1) 种选法，但只有 2∗i∗(n−i) 种选法会使 0 的数目发生变化.

也就是说，当前有 i 个 0 的时候，进行一次操作使得 0 的数目发生变化的概率 P[i] 可以直接算出来，是发生变化的方案数/总方案数

那么有 i 个 0 的时候，根据一个在概率期望题里常用的结论，期望操作 1/P[i] 次之后会使 0 的数目发生变化.

记 g[i]=1/P[i]

还有一个结论:如果某次操作使得 0 的数目变化了，那么 0 的数目 +1 和 -1 的概率都是0.5

显然，这时把一个 0 变 1 的方案数等于把一个 1 变 0的方案数，均为 i∗(n−i)

那么，对于 1<=i<=n-1 的 i，f[i]=g[i]+0.5∗f[i−1]+0.5∗f[i+1]

这样的方程组，不需要高斯消元求解，可以推推式子然后O(n)递推出来(类似HEOI2017Day2T2).

具体推法是:f[1]=g[1]+0.5∗f[0]+0.5∗f[2]=g[1]+0.5∗f[2]

于是我们把f[1]表示成了 k[1]∗f[2]+b[1] 的形式，其中k[1]，b[1]都已经求出来了.

f[2]=g[2]+0.5∗f[1]+0.5∗f[3]

之前我们把 f[1] 表示成了 k[1]∗f[2]+b[1] 的形式，现在就可以在f[2]的表达式里代入 f[1]=k[1]∗f[2]+b[1]

经过整理，就可以把 f[2]表示成k[2]∗f[3]+b[2] 的形式. 如此递推下去，最终可以把 f[n−1]表示为 k[n−1]∗f[n]+b[n−1] 的形式，而f[n]=0，此时便可依次回代，求出所有的f.

有多个数

考虑把 2 个数的方法拓展.如果从 0 到 30 枚举最终的数，那么就可以把所有数分成两类，和所枚举的最终数不同的数都可以认为是同一个数.我们求出最终的数是 0，1，2....30 的概率，然后分别求出最终数为 0，1，2....30时的期望步数，就可以方便地算出答案. 那么问题变成了两问:

最终的数是0，1，2....30 的概率

最终的数是0，1，2....30 的期望步数

第1问:

因为已经枚举了一个最终的数，假如这种最终的数现在有 i 个，那么问题相当于有 i 个 0 ，n-i 个 1，最终所有数变为 0 的概率. 记这个概率为 h[i].可以发现对不同的数，需要的h数组是相同的，所以h数组只需要求一遍. 那么边界h[0]=0，h[n]=1

转移方程是h[i]=0.5∗h[i−1]+0.5∗h[i+1]

同样可以用之前递推f[]的方法O(n)解方程组.实际上，解出来的h[i]=i/n，如果看出来这个规律就可以O(1)直接计算每个h[i]，如果没看出来写个O(n)解方程组也没事 (upd:这个规律其实非常有理有据，h[0]=0，h[n]=1，h[i]为等差数列)

第2问:

这一问是有点坑的.因为我们要求的是"最终的数是0，1，2....30的条件下，期望的步数"，那么这里是一个条件概率.

按照和第1问一样的思路，问题可以转化为"n个数有i个 0 ，n-i个 1，假如最后变为全 0，那么求走过的步数的期望f[i]"，同样这里的f[i]对所有不同的数都是一样的. 边界f[n]=0，此时f[0]没有意义.如果没有 0 ，无论如何也变不成全0.

一开始我没有注意到条件概率...把之前不要求结果为1/0的f[i]的方程组中 f[1]=g[1]+0.5∗f[0]+0.5∗f[2]改成了 f[1]=g[1]+f[2]，认为强制不能从f[0]转移过来就能解决问题. 然而这样完全是错的....这么算根本就没有什么实际意义....我们需要条件概率. 为啥是错的? 有i个 0 的时候，随机一个操作， 0 的个数+1/-1的概率都是0.5，是因为我们考虑所有可能的无限长的随机操作序列，在这些操作序列中恰好一半 0 的个数 +1，一半 0 的个数 -1 但是要求"最终变为全0"，概率就不一定是0.5了.不是所有无限长操作序列都使得最终变为全0，所以要用到条件概率. 关键在于:有i+1个 0 和i-1个 0 的状态最终能够达到全0状态的概率是不同的，分别是(i+1)/2n和(i-1)/2n.因此，可以大致理解为:如果我们多次重复做这样的操作(每次都是从i个 0 开始随机操作直到所有的数都相同)，每(i+1)+(i-1)=2i次到达全0状态的结果中，平均有(i+1)次是第一步从i个 0 变成i+1个 0 ，有i-1次是第一步从i个 0 变成i-1个 0 . 因此方程应该写作 f[i]=g[i]+(i+1)/(2i)∗f[i+1]+(i−1)/(2i)∗f[i−1]

这样再O(n)解方程组就没问题了.