如何入手概率期望题呢?

Description

一个缓存最多只能容纳$k$个元素, 如果超过$k$个, 则最早进入缓存的会被弹出. 现在有$n$个元素, 每次选择元素$i$的概率是$p_i$, 然后把这个元素放入缓存. 问无穷多次操作后, 每个元素在缓存中的概率是多少.

Solution

首先没法顺推, 每次考虑下一步做什么转移过于麻烦. 无穷多意味着只有最后若干次选择影响了结果, 我们不妨倒推, 枚举最后选择的$k$种物品是什么, 以求出概率. 因为无穷多次操作下, $k$个位置不被占满的概率趋近于0, 所以我们只让占满的状态对答案贡献. 考虑一个不满的状态, 从没有出现的元素中选择一个, 从当前状态到选出这个元素之间可能隔着若干次选中已存在的元素的操作, 但一定不存在选中其他未选中的元素的操作, 所以概率为$\frac{p_i}{\sum{所有未选中的元素概率}}$.

那么有: $P(s | 2^{i-1}) += P(s) \times \frac{p_i}{\sum_{unchosen}{p}}$.

这时每个选满$k$个元素的状态都对应着几条从倒数若干步选到最后一步的路径.

需要注意特殊处理概率为$0$的元素, 保证让他们不会被选中. 令$k$对非零元素个数取$\min$. 至于为什么是这样也没人讲清楚

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;
typedef long double ldb;

const int maxs = 1048577;
const int maxn = 21;
const ldb eps = 1e-10;

int n, k, m;
ldb f[maxs], p[maxn], ans[maxn];

inline void solve(int st) {
  int popcnt = 0; ldb sum = 0.0;
  for (int i = 1; i <= n; ++i) {
    if (st & (1 << (i - 1))) popcnt++;
    else sum += p[i];
  }
  if (popcnt > k) return;
  else if (popcnt == k) {
    for (int i = 1; i <= n; ++i)
      if (st & (1 << (i - 1))) ans[i] += f[st];
  } else {
    for (int i = 1; i <= n; ++i)
      if (!(st & (1 << (i - 1)))) {
        int it = st | (1 << (i - 1));
        f[it] += f[st] * (p[i] / sum);
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> n >> k; m = n;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    if (p[i] < eps) m--;
  }
  k = min(k, m);
  int lim = (1 << n) - 1;
  f[0] = 1.0;
  for (int i = 0; i <= lim; ++i)
    solve(i);
  for (int i = 1; i <= n; ++i)
    cout << fixed << setprecision(15) << ans[i] << " ";
  return 0;
}