P5516 [MtOI2019] 小铃的烦恼 题解

· · 题解

Solution

这是一篇与其他题解有所不同的题解。最终并不需要使用高斯消元。

首先，问题可以转化为有 n 种不同颜色的小球，每种颜色有 a_i 个，每次选取两个球进行染色，求所有颜色相同的期望步数。下文中 s 表示 \sum_{i = 1}^n a_i。

接着，设 dp_i 表示已知有 i 个球为钦定的颜色，最后所有的颜色均为该钦定颜色的期望步数。

显然对于每一次操作，对于钦定的颜色 x，有以下几种结果：

  1. 该颜色数量增加，从 dp_{i - 1} 转移来，概率为 \frac{i(s - i)}{s(s - 1)}。

  2. 该颜色数量减少，从 dp_{i + 1} 转移来，概率为 \frac{i(s - i)}{s(s - 1)}。

  3. 该颜色数量不变，从 dp_{i} 转移来，概率为 1 - \frac{2i(s - i)}{s(s - 1)}。

综合以上可以得出下面的转移式：

dp_i = \frac{i(s - i)}{s(s - 1)}dp_{i - 1} + \frac{i(s - i)}{s(s - 1)}dp_{i + 1} + (1 - \frac{2i(s - i)}{s(s - 1)})dp_i + w_i

注意到 w_i 表示该情况下对答案的期望贡献，即以该钦定颜色为最终颜色的概率。

考虑 w_i 有以下关系。

w_0 = 0 \text{，} w_s = 1 \newline w_i = \frac{i(s - i)}{s(s - 1)}w_{i - 1} + \frac{i(s - i)}{s(s - 1)}w_{i + 1} + (1 - \frac{2i(s - i)}{s(s - 1)})w_i

将上式稍加变化即可得到：

w_{i + 1} - w_i = w_i - w_{i - 1} \newline w_i = \frac{i}{s}

带入之前的式子可得：

dp_i = \frac{i(s - i)}{s(s - 1)}dp_{i - 1} + \frac{i(s - i)}{s(s - 1)}dp_{i + 1} + (1 - \frac{2i(s - i)}{s(s - 1)})dp_i + \frac{i}{s}

注意，接下来我们的方法便出现了不同。

类似对 w_i 进行变换的，我们对 dp_i 的式子稍加变换得到：

dp_{i + 1} = 2dp_i - dp_{i - 1} - \frac{s - 1}{s - i}

也就是说我们得到了 dp_i 的递推形式而不是带环的方程。

考虑 dp_1 的值，我们可以得到以下的式子。

dp_s = 0 \newline dp_1 = dp_1 - dp_s = \sum\limits_{i = 2}^s dp_i - dp_{i - 1} \newline dp_1 = (s - 2)(s - 1) + (s - 1)(dp_1 - dp_2)

当 i = 1 时，由于 dp_0 = 0，dp_2 = 2dp_1 - 1。带入上式得到 dp_1 = \frac{(s - 1)^2}{s}，dp_2 = \frac{2(s - 1)^2}{s} - 1。

然后线性递推即可。

注意到，dp_x = \sum\limits_{i = 2}^x \frac{x - i + 1}{i - s + 1}。这个东西我们在分块之后多项式多点求值可以做到 O(\sqrt{V} \log^2V + n\sqrt{V})，其中 V 为 x 的值域，当 V 很大时似乎更优更劣了。

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n, sum[MAXN];
char s[MAXN];
double dp[MAXN];
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') 
           f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int maxn = 0;
    for (int i = 1; i <= n; i++) sum[s[i] - 'A' + 1]++, maxn = max(maxn, sum[s[i] - 'A' + 1]);
    dp[1] = 1.0 * (n - 1) * (n - 1) / n, dp[2] = 2.0 * dp[1] - 1.0;
    for (int i = 3; i <= maxn; i++) dp[i] = 2 * dp[i - 1] - dp[i - 2] - 1.0 * (n - 1) / (n - i + 1);
    double ans = 0;
    for (int i = 1; i <= 26; i++) ans += dp[sum[i]];
    printf("%0.1lf\n", ans);
    return 0;
}