T1 Color
https://gxyzoj.com/d/hzoj/p/3692
显然，答案与元素的位置无关，只与个数有关
考虑每个元素能经过若干次操作变成n个的概率，记\(p_i\)为i个数能变到n个数的概率
进行一次操作后，会分成三种情况，+1，-1,和不变，所以式子是：
\[p_i=\dfrac{i(n-i)}{n(n-1)} p_{i-1}+\dfrac{i(n-i)}{n(n-1)} p_{i+1}+(1-2 \dfrac{i(n-i)}{n(n-1)}) p_i \]化简得：\(p_i=\dfrac{p_{i-1}+p_{i+1}}{2}\)
去分母，得：\(2p_i=p_{i-1}+p_{i+1}\)
即：\(p_i-p_{i-1}=p_{i+1}-p_i\)
所以，转移到n的概率为等差数列，因为\(p_0=0,p_n=1\)，所以，\(p_i=\dfrac{i}{n}\)
接下来考虑期望，记\(f_i\)表示当前种类目前有i个，转移到n还需的期望次数
根据概率，单次改变数值的概率为\(2 \dfrac{i(n-i)}{n(n-1)}\)，所以改变数值的期望次数即为其倒数\(\dfrac{n(n-1)}{2i(n-i)}\)
因为并不是所有情况都能转移到n，所以要乘上一定的概率，并且由概率，可以知道从\(i+1\)和\(i-1\)转移的概率是相等的，所以要乘以\(\dfrac{1}{2}\)，所以式子是:
\[p_i f_i=p_i \dfrac{n(n-1)}{2i(n-i)}+\dfrac{1}{2}(p_{i-1} f_{i-1}+p_{i+1} f_{i+1}) \] 标签：总结,概率,比赛,所以,dfrac,个数,2i,20240519,转移 From： https://www.cnblogs.com/wangsiqi2010916/p/18200771