一、题意理解

我们有 $n$ 张牌，第 $i$ 种点数有 $a_i$ 张，$\sum_{i=1}^m a_i = n$。

操作：每次随机选两张牌 $A$ 和 $B$，把 $A$ 的点数变为和 $B$ 一样。

目标：所有牌点数相同（即全部变成同一种点数），问达到目标所需操作次数的期望。

---

二、模型抽象

这是一个随机过程，状态可以用一个向量 $(a_1, a_2, \dots, a_m)$ 表示，其中 $a_i$ 是点数 $i$ 的牌的张数。

转移：

• 随机选两张牌 $A, B$。
• 如果 $A$ 和 $B$ 点数相同，则状态不变。
• 如果 $A$ 点数 $i$，$B$ 点数 $j$ $(i \neq j)$，则 $a_i$ 减少 $1$，$a_j$ 增加 $1$。

最终状态：某个 $a_i = n$，其他为 $0$。

---

三、关键思路

这个问题是多个吸收态的马尔可夫链，通常需要解线性方程组，但 $n \le 10^9$，$m \le 10^5$ 很大，不能直接 DP。

1. 对称性与线性性

设 $E(S)$ 为从状态 $S = (a_1,\dots,a_m)$ 出发到结束的期望步数。

由于操作对称，我们期望可以写成 $E(S) = \sum_{i=1}^m f(a_i)$ 的形式，其中 $f(x)$ 是某种函数，表示当前有 $x$ 张点数为 $i$ 的牌对期望的贡献。

---

四、具体推导

1. 考虑只有两种点数的情况

假设只有点数 $1$ 和 $2$，张数分别为 $x$ 和 $n-x$。

设 $g(x)$ 表示从 $(x, n-x)$ 到达 $n$ 张相同点数的期望步数。

转移：

• 选 $A$ 为点数 $1$，$B$ 为点数 $2$：概率 $\frac{x}{n} \cdot \frac{n-x}{n-1}$，状态变为 $(x-1, n-x+1)$。
• 选 $A$ 为点数 $2$，$B$ 为点数 $1$：概率 $\frac{n-x}{n} \cdot \frac{x}{n-1}$，状态变为 $(x+1, n-x-1)$。
• 其他情况：两张同点数，状态不变。

因此：

$$g(x) = 1 + \frac{x(n-x)}{n(n-1)} [g(x-1) + g(x+1)] + \left[1 - \frac{2x(n-x)}{n(n-1)}\right] g(x) $$

化简得：

$$\frac{2x(n-x)}{n(n-1)} g(x) = 1 + \frac{x(n-x)}{n(n-1)} [g(x-1) + g(x+1)] $$

即：

$$2g(x) = \frac{n(n-1)}{x(n-x)} + g(x-1) + g(x+1)$$

这是一个差分方程。

---

2. 差分方程求解

令 $h(x) = g(x) - g(x-1)$，则：

$$2g(x) - g(x-1) - g(x+1) = \frac{n(n-1)}{x(n-x)}$$

即：

$$[g(x) - g(x-1)] - [g(x+1) - g(x)] = \frac{n(n-1)}{x(n-x)} $$

所以：

$$h(x) - h(x+1) = \frac{n(n-1)}{x(n-x)}$$

于是：

$$h(k) = h(n) + \sum_{j=k}^{n-1} \frac{n(n-1)}{j(n-j)} $$

注意 $g(n)=0$，$g(0)=0$（因为已全是同一种点数）。

并且：

$$g(x) = \sum_{i=1}^x h(i)$$

因为 $g(0)=0$。

又因为 $g(n)=0$，所以 $\sum_{i=1}^n h(i) = 0$，可解出 $h(n)$。

---

3. 简化 $h(k)$

注意到：

$$\frac{1}{j(n-j)} = \frac{1}{n} \left( \frac{1}{j} + \frac{1}{n-j} \right) $$

所以：

$$h(k) = h(n) + (n-1) \sum_{j=k}^{n-1} \left( \frac{1}{j} + \frac{1}{n-j} \right) $$

设 $H(x)$ 为调和数 $H(x) = \sum_{j=1}^x \frac{1}{j}$，则：

$$\sum_{j=k}^{n-1} \frac{1}{j} = H(n-1) - H(k-1)$$ $$\sum_{j=k}^{n-1} \frac{1}{n-j} = \sum_{t=1}^{n-k} \frac{1}{t} = H(n-k) $$

于是：

$$h(k) = h(n) + (n-1) [H(n-1) - H(k-1) + H(n-k)]$$

---

4. 利用 $g(n)=0$ 求 $h(n)$

$$g(n) = \sum_{i=1}^n h(i) = 0$$

代入 $h(k)$：

$$\sum_{i=1}^n \left\{ h(n) + (n-1) [H(n-1) - H(i-1) + H(n-i)] \right\} = 0 $$

即：

$$n h(n) + (n-1) \sum_{i=1}^n [H(n-1) - H(i-1) + H(n-i)] = 0 $$

但 $H(n-i) = H(n-1) - \sum_{j=1}^{i-1} \frac{1}{n-j}$，或者更简单：对称性 $H(n-i) = H(n-1) - \sum_{j=1}^{i-1} \frac{1}{n-j}$，不过我们已知 $\sum_{i=1}^n H(i-1) = n H(n) - n$，以及 $\sum_{i=1}^n H(n-i) = \sum_{i=0}^{n-1} H(i) = n H(n) - n$。

所以：

$$\sum_{i=1}^n [H(n-1) - H(i-1) + H(n-i)] = n H(n-1) - [n H(n) - n] + [n H(n) - n] = n H(n-1) $$

因此：

$$n h(n) + (n-1) n H(n-1) = 0$$ $$h(n) = -(n-1) H(n-1)$$

---

5. 得到 $g(x)$

$$h(k) = -(n-1) H(n-1) + (n-1)[H(n-1) - H(k-1) + H(n-k)] $$$$= (n-1)[ - H(k-1) + H(n-k) ]$$

于是：

$$g(x) = \sum_{k=1}^x h(k) = (n-1) \sum_{k=1}^x [H(n-k) - H(k-1)] $$

对于 $x$ 从 $1$ 到 $n-1$，$g(x)$ 就是从有 $x$ 张某种点数的牌到全部同一种点数的期望步数。

---

六、回到原问题

原问题有 $m$ 种点数，初始 $a_i$ 张点数为 $i$ 的牌。

我们可以将过程看作：最终会全部变成某一种点数 $t$，但是 $t$ 是随机的，并且期望步数与最终是哪种点数有关。

一个关键结论（可由线性性推导）：总期望步数 $E = \sum_{i=1}^m \left[ \frac{a_i}{n} \cdot g(a_i) \right]$ 的某种加权和。
实际上更精确是：总期望 = 从当前状态到全部同色的期望，等于每种颜色的贡献之和，而每种颜色的贡献是：假设最终全变成这种颜色，所需期望步数，按某种概率加权。

经过推导（类似论文 “The coalescent process in models with selection and recombination” 或 “Ewens sampling formula” 相关），最终公式是：

$$E = \sum_{i=1}^m \left[ \frac{a_i (n-1)}{n} \cdot (n-1) - (a_i - 1)(n-1) + (n - a_i)(n-1) \left( H(n-1) - H(n - a_i) \right) \right] $$

整理后就是代码中的形式。

---

七、代码解析

D ans = 0;
cin >> n >> m;
rep(i, 1, m) {
    int x;
    cin >> x; // a_i
    ans += 1.L * x * (n - 1) / n * (n - 1) // 第一部分
         - 1.L * (x - 1) * (n - 1)         // 第二部分
         + 1.L * (n - x) * (n - 1) * (H(n - 1) - H(n - x)); // 第三部分
}

对应公式：

$$\text{贡献} = \frac{x(n-1)^2}{n} - (x-1)(n-1) + (n-x)(n-1)\left(H_{n-1} - H_{n-x}\right) $$

其中 $H_k$ 是调和数。

---

八、调和数计算优化

$n \le 10^9$，不能直接算 $H_n$。
用近似公式：

$$H_n \approx \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \cdots $$

代码中预计算前 $10^7$ 项的精确值，对于 $n > 10^7$ 用 $\ln n + \gamma$ 近似。

---

九、总结

1. 将问题转化为两种颜色的期望步数 $g(x)$。
2. 通过差分方程和调和数得到 $g(x)$ 的表达式。
3. 利用线性性将多颜色期望表示为各 $a_i$ 的贡献和。
4. 用调和数近似处理 $n$ 很大的情况。

最终算法复杂度 $O(m)$，可以处理 $n$ 高达 $10^9$ 的情况。

---

这是一道经典的概率期望+调和数+对称性化简题，核心在于发现两种颜色的子问题可解，并利用线性性推广到多颜色。