题意
有 \(n\) 个球，\(m\) 种颜色，\(i\) 种颜色有 \(a_i\) 个球。
每次随机选择两个球 \(x\)，\(y\)。使两个球的颜色都变为 \(y\) 的颜色。
问最终只有一个颜色的球的期望步数。
\(n \le 10 ^ 9, m \le 10 ^ 5\)。
Sol
显然的，考虑先枚举最终颜色，我们只关心当前有多少个最终颜色的球。
于是设 \(f_i\) 表示当前有 \(i\) 个最终颜色的球，最终获胜的期望步数的贡献。
\(f_0 = 0, f_n = 0\)，答案就是 \(\sum_{f_{a_i}}\)。
注意到实际上当前情况是有概率不会获胜，也就是无法全部变为最终颜色的球的，很影响我们进行 \(\texttt{dp}\)。
于是先设 \(g_i\) 表示当前有 \(i\) 个最终颜色的球的获胜概率，\(g_0 = 0, g_n = 1\)。
由于是概率，自己不会对自己产生贡献，可以写出转移：\(g_i = \frac{g_{i - 1} + g_{i + 1}}{2}\)。
集中注意力可以发现 \(g_i = \frac{i}{n}\)。
回到 \(f\)，考虑计算当前状态会产生变化的期望步数。
设一次操作状态没有变化的概率为 \(p\)，\(q = 1 - p\) 有：
\[q = \frac{2 \times i \times (n - i)}{n \times (n - 1)} \]期望步数为：
\[\sum_{i = 0} ^ {\infty} (i + 1) p ^ i q \]Lemma. \(\sum_{i = 0} ^ {\infty} k ^ i = \frac{1}{1 - k}\)
同理，设 \(s = \sum_{i = 0} ^ {\infty} (i + 1) p ^ i\)。
可得：\(p s + \frac{1}{1 - p} = s\)，解得 \(s = \frac{1}{(1 - p) ^ 2}\)。
那么就是：
\[\frac{q}{(1 - p) ^ 2} \]然后这个东西需要乘上 \(g_{i - 1}\) 和 \(g_{i + 1}\)。
于是就是：
\[\frac{1}{2} \times (\frac{q(i - 1)}{(1 - p) ^ 2 n} + \frac{q(i + 1)}{(1 - p) ^ 2 n}) \]代入 \(f\)：
\[f_i = \frac{1}{2}(f_{i - 1} + f_{i + 1}) + \frac{n - 1}{2 \times (n - i)} \]移一下，写成递推式。
\[f_i = 2 f_{i - 1} - f_{i - 2} - \frac{n - 1}{n - i + 1} \]使用膜法/暴力展开/集中注意力。
\[f_i = i \times f_1 - \sum_{j = 1} ^ {i - 1} j \times \frac{n - 1}{n - i + j} \]由于我们知道 \(f_n = 0\)，代入解得 \(f_1 = \frac{(n - 1) ^ 2}{n}\)。
把式子再变一下就可以做了，注意到 \(\sum\) 里面把 \(n - 1\) 提出来是一个上指标乘调和级数。
直接用 \(1\) 减去她，代入调和级数：
\[f_i = \frac{i \times (n - 1) ^ 2}{n} + (n - 1)((n - i) \times (H_{n - 1} - H_{n - i}) - i + 1) \]这样就做完了，复杂度瓶颈在于调和级数的计算。
有个小 \(\texttt{trick}\) 就是调和级数近似于 \(\ln + 0.577\)，直接暴力计算即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
#define ld long double
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
bool _stmer;
const int N = 1e6 + 5;
array <ld, N> h;
ld H(int x) {
if (x > 1e6) return log(x) + 0.577;
else return h[x];
}
bool _edmer;
int main() {
cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
for (int i = 1; i <= 1e6; i++)
h[i] = h[i - 1] + 1.0 / i;
int n = read(), q = read();
ld ans = 0;
while (q--) {
ld x = read();
ans += (ld)x * (n - 1) * (n - 1) / n + (n - 1) * (n - x) * (H(n - 1) - H(n - x)) - (n - 1) * (x - 1);
}
printf("%.8Lf\n", ans);
return 0;
}