LOJ#6118 鬼牌

$\mathrm{u}\mathrm{p}\mathrm{d}$：是我假了...这题没有爆精...大家要记得这道题是相对误差${10}^{-6}$...感谢@foreverlasting的指正。

题是好题，可是标算爆精是怎么回事...要写的和标算一毛一样才能过。

各位要写的话过了前5个点就当过了吧...

题意

你有$n$张牌，每张牌上有一个$1\sim m$的点数，你每次随机选出两张不同的牌$A$和$B$，并将$A$的点数变为$B$的点数。求将所有牌的点数变成一样的期望步数。用$double$输出。$n\le {10}^9$，$m\le {10}^5$。

题解

那首先有个挺显然的想法是枚举最终变成了哪种牌，那么所有牌就变成了是这种牌与不是这种牌两类。我们这么计算这种情况的贡献：

假如若干步以后，是这种牌的数量变为$0$，则这种情况的贡献为$0$。 否则，若干步以后是这种牌的数量变为$n$，则这种情况的贡献为$\mathrm{发}\mathrm{生}\mathrm{的}\mathrm{概}\mathrm{率}\ast \mathrm{步}\mathrm{数}$。

那么只要把每种牌的这个答案加起来就好了。

现在我们要解决的问题是：有两种牌，第一种有$i$张，第二种有$n-i$张，问最终全变为第一种牌的贡献。

很显然当$n$固定的时候，答案只和$i$有关。于是我们将其记为$f_i$。

在计算$f_i$之前，我们先来计算辅助数组$g$。其中$g_i$表示有两种牌，第一种有$i$张，第二种有$n-i$张，问最终全变为第一种牌的概率。

怎么求$g_i$呢？首先边界条件有$g_0=0$，$g_n=1$，再来考虑一般的情况。

我们来考虑一下第一次对牌数有影响的操作。假如$A$是第一种牌，$B$是第二种牌，那么第一种牌数$-1$；假如$A$是第二种牌，$B$是第一种牌，那么第一种牌数$+1$。显然这两种情况的方案数是一样的，于是可以得出$i$会等概率变成$i-1$或$i+1$，于是就可以得到一个简单的式子：

$$g_i=\frac{1}{2}(g_{i-1}+g_{i+1})$$

于是移项得到：

$$g_{i+1}=2\ast g_i-g_{i-1}$$

可以发现每一项都依赖前两项，于是我们设$g_1=x$，则可计算出$g_2=2\ast x$，$g_3=3\ast x$，$\dots$，那么显然我们可以猜想$g_i=i\ast x$，可以通过归纳法证明其是成立的。

于是得到$g_n=n\ast x=1$，解得$x=\frac{1}{n}$。

因此当第一种牌数为$i$时，最终全变成第一种牌的概率为$\frac{i}{n}$。

现在来考虑求$f_i$，边界条件有$f_0=0$，$f_n=0$，一般情况显然还是可以归纳成$f_{i-1}$和$f_{i+1}$的情况。不过这次还要额外考虑一些事情：

以变成$i-1$为例，首先我们枚举在几步以后变成$i-1$。设没有影响的操作发生概率为$p$，使$i$变为$i-1$的操作发生概率为$q$。则可得到期望额外花费的步数为：

$$\sum _{j\ge 0}((j+1)\ast p^j\ast q)$$

整理得其为$\frac{q}{(1-p{)}^2}$。

还要注意的是由于规约到$i-1$的情况后成功的概率是$\frac{i-1}{n}$，而失败的贡献是$0$，因此期望步数只有$\frac{i-1}{n}$是有效的，贡献为$\frac{q}{(1-p{)}^2}\ast \frac{i-1}{n}$。

对于$i+1$的情况，$p$和$q$是一样的，因此贡献为$\frac{q}{(1-p{)}^2}\ast \frac{i+1}{n}$。两者相加为$\frac{q}{(1-p{)}^2}\ast \frac{2\ast i}{n}$。

可以计算得$1-p=\frac{2\ast i\ast (n-i)}{n\ast (n-1)}$，$q=\frac{i\ast (n-i)}{n\ast (n-1)}$。于是原式可化简为：

$$\frac{n-1}{2\ast (n-i)}$$

因此可以得到：

$$f_i=\frac{1}{2}(f_{i-1}+f_{i+1})+\frac{n-1}{2\ast (n-i)}$$

移项可得：

$$f_{i+1}=2\ast f_i-f_{i-1}-\frac{n-1}{n-i}$$

依然设$f_1=x$，则$f_2=2\ast x-\frac{n-1}{n-1}$，$f_3=3\ast x-2\ast \frac{n-1}{n-1}-\frac{n-1}{n-2}$，$\dots$，依然可以通过观察和归纳法证明：

$$f_i=i\ast x-\sum _{j=1}^{i-1}((i-j)\ast \frac{n-1}{n-j})$$

那么对于$f_n$：

$$f_n=n\ast x-\sum _{j=1}^{n-1}((n-j)\ast \frac{n-1}{n-j})=0$$

可解得$x=\frac{(n-1)\ast (n-1)}{n}$。

于是继续对$f_i$的式子进行化简：

$$f_i=i\ast \frac{(n-1)\ast (n-1)}{n}-i\ast (n-1)\ast (\sum _{j=1}^{i-1}\frac{1}{n-j})+(n-1)\ast (\sum _{j=1}^{i-1}\frac{j}{n-j})$$

我们设$H_i$为调和数，即$H_i=\sum _{j=1}^i\frac{1}{j}$，则第二项等于：

$$-i\ast (n-1)\ast (H_{n-1}-H_{n-i})$$

继续推导第三项：

$$(n-1)\ast (\sum _{j=1}^{i-1}\frac{j}{n-j})$$$$(n-1)\ast (\sum _{j=1}^{i-1}(\frac{n}{n-j}-1))$$$$(n-1)\ast n\ast (\sum _{j=1}^{i-1}\frac{1}{n-j})-(n-1)\ast (i-1)$$$$(n-1)\ast n\ast (H_{n-1}-H_{n-i})-(n-1)\ast (i-1)$$

将三项合并，最终得到：

$$f_i=i\ast \frac{(n-1)\ast (n-1)}{n}+(n-1)\ast (n-i)\ast (H_{n-1}-H_{n-i})-(n-1)\ast (i-1)$$

那么问题来了，$n$那么大，$H_n$怎么求呢？标算的做法是将小的调和数预处理，大的用$H_x\simeq \ln x+\gamma$来近似，其中$\gamma$为欧拉常数。但是不知道为啥标算的$\gamma$取的是$0.57$...不过实测下来就算预处理前$2^{20}$的调和数以及用较精确的欧拉常数后面的误差也在${10}^{-7}$左右...再乘以一个大常数算答案精度堪忧。

这里再提供一个精度靠谱复杂度也有保证的做法。注意到答案中计算贡献的调和数其实类似于倒数的后缀和，因此$i$较小的时候显然可以预处理。可以设一个阈值$T$，预处理前$T$个后缀和，剩下的数不会超过$\frac{n}{T}$个，可以用分段打表暴力处理。由于查询量不是很大，打表的间隔可以取大一点减少代码长度。

还有由于答案有点大最好开$longdouble$或者自己写精度更高的类型...~~不过反正标算都爆精了这些好像也是后话了。~~这么好的题为什么不取模呢，用第二种做法就很靠谱了。