[LOJ#6188]「2017 山东二轮集训 Day7」鬼牌

题意

有 \(n\) 张牌，每张牌上有一个\(1\sim m\)的点数，最开始点数为 \(i\) 的牌有\(a_i\) 张

每次你会随机选两张不同的牌 \(A,B\)，并把 \(A\) 的点数变成 \(B\) 的点数

求所有牌的点数变成一样的期望步数

\(n\le 1e9,m\le 1e5\)

题解

我们首先枚举最后变成了哪种牌，那么所有牌都变成了是这种牌或者不是这种牌两种关系。我们计算这种情况的贡献即可。

假如若干步之后，数量变成0，那么贡献为0，否则，步数为\(n\)，那么这时候贡献为 \(nE(x)\).

考虑首先求出来那个：\(g(i)\) 表示刚开始有 \(i\) 个，然后最后全是这个颜色的概率。首先我们可以猜测是 \(\frac{num}{n}\)，因为每种颜色类似。

证明一下：我们有 \(g(0)=0,g(n)=1\)

并且，一次可能把这玩意颜色数量加一或者减一，那么就是

\[g(i)=\frac{1}{2} (g(i-1)+g(i+1)) \]

这玩意可以退出来 \(g(i)=\frac{i}{n}\)。

我们在考虑求出来 \(f(i)\) 即题目所求。

首先 \(f(0)=0,f(n)=1\)

然后看看能不能做出来 \(f(i),f(i-1),f(i+1)\) 的关系。

我们考虑什么时候多一个少一个之类的、

那么就是设操作一次之后颜色数量没有变化的概率为 \(p\)，否则为 \(q\)。

那么期望走的步数就是

\[\sum_{j\ge 0}(j+1)p^jq \]

那么就是

\[\frac{q}{(1-p)^2} \]

还要注意的是可能约束到 \(i-1\) 的情况后成功的概率是 \(\frac{i-1}{n}\)。

所以应该是 \(\frac{q(i-1)}{(1-p)^2n}\)。

然后另一个就是 \(\frac{q(i+1)}{(1-p)^2n}\)

那么就是

\[f_i=\frac{1}{2}(f_{i-1}+f_{i+1})+\frac{n-1}{2\times(n-i)} \]

这玩意，然后

\[f_{i+1}=2f_i-f_{i-1}-\frac{n-1}{n-i} \]

然后，设 \(f_1=x\),

那么

\[f_i=ix-\sum_{j=1}^{i-1}((i-j)\times \frac{n-1}{n-j}) \]

然后

\[x=\frac{(n-1)^2}{n} \]

然后，

\[f_i=\frac{i(n-1)^2}{n}+(n-1)(n-i)(H_{n-1}-H_{n-i})-(n-1)(i-1) \]

然后做完了。