P5516 [MtOI2019] 小铃的烦恼-526互联

link：P5516 [MtOI2019] 小铃的烦恼

题意

给定 \(n\) 个字符，每次操作可以随机的选出两个字符 \(S_a, S_b\) 使得 \(S_a = S_b\)，问将所有字符变成相同字符所需要的期望步数。

\(n \leqslant 2 \times 10^3\)

Solution

显然答案对于每个字符是独立且等价的，那么不妨枚举选出的字符，将他们的期望求和就能得出答案，下面依次考虑每一种字符。

因为每次选择是完全随机的，显然对于某个状态，并不一定能够变成全部字符为某个特定字符的状态，不妨计算一下能够全部成为特定字符的概率，记 \(S\) 中有 \(i\) 个特定字符能够成功转化的概率为 \(p_i\)

\[p_i = \frac{i · (n - i)}{n · (n - 1)} · p_{i - 1} + \frac{i · (n - i)}{n · (n - 1)} · p_{i - 1} + (1 - 2· \frac{i · (n - i)}{n · (n - 1)}) · p_{i} \]

\[\Rightarrow p_i = \frac{p_{i - 1} + p_{i + 1}}{2} \]

则有 \(p\) 为等差数列，因为\(p_0 = 0, p_n = 1\)，则\(p_i = \frac{i}{n}\)。

接下来，计算步骤的期望，记 \(S\) 中有 \(i\) 个特定字符能够成功转化的操作次数期望为 \(f_i\)

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

解释一下， \(f_i\) 状态能够成功的步数首先是在能成功的前提下的，也就是只有 \(p_i\) 的概率能够有可能产生答案，所有说后面的状态转移都需要乘上该状态最终能够成功的概率，对于每一步变化 \(\pm 1\) 的概率是 \(2 · \frac{i · (n - i)}{n · (n - 1)}\)，显然操作的期望为上面概率的倒数，而又上面计算 \(p_i\) 的式子可知，产生 \(+1, -1\) 的概率是相等的，所以说能够进入对应状态的概率应乘以 \(\frac{1}{2}\)

整理一下式子，则有，

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

因为有 \(n\) 个式子，可以考虑使用高斯消元求解 \(f_i\) 的值，得到如下矩阵

\[\begin{bmatrix} -1 & \frac{1}{2} & 0 & \cdots & 0 & -\frac{n}{2} \\ \frac{1}{4} & -1 & \frac{3}{4} & \cdots & 0 & -\frac{n·(n - 1)}{4 · (n - 2)} \\ 0 & \frac{1}{4} & -1 & \cdots & 0 & -\frac{n·(n - 1)}{6 · (n - 3)} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & -1 & -1 \end{bmatrix} \]

显然使用高斯消元 \(O(n^3)\) 的时间复杂度是不能接受的，可以发现每行只有三个元素，可以针对这三个元素进行消元，时间复杂度为\(O(n)\)。

\[ans = \sum_{i = A}^{Z} \frac{num_i}{n} · f_{num_i} \]

Code

点击查看代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

const int N = 2e3 + 50, M = 4e5 + 50;

inline int read() {
	register int w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n;
int cnt[30];
char s[N];
double ans;
double b[N], f[N], w[N];

int main() {
	scanf ("%s", s + 1);
	n = strlen (s + 1);
	for (register int i = 1; i <= n; ++ i)  cnt[s[i] - 'A'] ++;
	b[1] = 1;
	for (register int i = 1; i < n; ++i)  w[i] = -1.0 * n * (n - 1) / (2.0 * i * (n - i));
	for (register int i = 2; i < n; ++i) {
		w[i] += 1.0 * (i - 1) / (2 * i) * w[i - 1];
		register double dv = 1 - 1.0 * (i - 1) / (2 * i) * b[i - 1];
		b[i] = 1.0 * (i + 1) / (2 * i) / dv;
		w[i] /= dv;
	}
	f[n] = 0;
	for (register int i = n - 1; i >= 1; --i)  f[i] = b[i] * f[i + 1] - w[i];
	for (register int i = 0; i < 26; ++i)  ans += 1.0 * cnt[i] / n * f[cnt[i]];
	printf("%.1lf\n", ans);
	return 0;
}

corporate finance fins 5516