「MtOI2019」小铃的烦恼 概率/期望+线性高斯消元

简单的讲一讲。

我们可以钦定某一个魔法属性，使得这个魔法属性是最终的属性。

那么其贡献很显然就是该属性变为最终属性的概率$\times$该属性变为最终属性所需要的期望步数 。

将其依次求出。

---

概率。

很显然如果当前局面有 $i$ 个当前魔法属性，那么这一次操作有 $\frac{2i(n-i)}{n(n-1)}$ 的概率使得 $i$ 变化，其中 $\frac{i(n-i)}{n(n-1)}$ 的概率使得 $i$ 加 $1$ ，$\frac{i(n-i)}{n(n-1)}$ 的概率使得 $i$ 减 $1$ 。

设 $p_i$ 表示当前有 $i$ 个答案魔法属性时，钦定的魔法属性变为最终答案的概率。

可以得到 $p_i=\frac{p_{i-1}+p_{i+1}}{2}$ ，因为是等差数列，所以可以得到 $p_i=\frac{i}{n}$ 。

---

期望。

设 $f_i$ 表示当前有 $i$ 个答案魔法属性时，钦定的魔法属性变为最终答案的期望步数。

注意这是条件期望，也就是说转移的时候对于 $f_{i-1}$ 和 $f_{i+1}$ 我们不能给其分配一样的概率，毕竟两个状态到最终状态的概率不一样。

所以转移方程为：

$$f_i=\frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}{f}_{i-1}+\frac{i+1}{2i}{f}_{i+1}$$

这样直接用线性高斯消元即可，复杂度 $O(n)$ 。

---

代码。

• #include <cstdio>

  #include <string>

  #include <iostream>

  #include <algorithm>

  using namespace std;

  
  

  const int N = 1e4 + 2;

  
  

  double f[N], a[N], b[N], inv, num, ans;

  int n, tot[27];

  char s[N];

  
  

  int main()

  {

  scanf("%s", s + 1);

  for (n = 1; s[n]; ++n)

  ++tot[s[n] - 'A'];

  --n, a[1] = 1, b[1] = 0.5 * n;

  for (int i = 1; i <= n; ++i)

  for (int j = 1; j <= n; ++j)

  scanf("%lf", &inv);

  for (int i = 2; i < n; ++i)

  {

  inv = 0.5 / i, num = 1.0 / (1 - (i - 1) * inv * a[i - 1]);

  a[i] = (i + 1) * inv * num;

  b[i] = ((i - 1) * inv * b[i - 1] + n * (n - 1) * inv / (n - i)) * num;

  }

  for (int i = n - 1; i >= 1; --i)

  f[i] = a[i] * f[i + 1] + b[i];

  for (int i = 0; i < 26; ++i)

  ans += 1.0 * tot[i] / n * f[tot[i]];

  printf("%.1lf\n", ans);

  return 0;

  }
• }
• }