题解 CF698C【LRU】
题目描述
有 \(n\) 种物品和大小为 \(k\) 的队列。每次操作，以 \(p_i\) 的概率选择第 \(i\) 种物品放入队尾，如果已经有物品 \(i\) 了就将物品 \(i\) 拿出来扔到队尾。若队列大小 \(\gt k\) ，弹出队首。
求 \(10^{100}\) 次操作后每种物品在队列里的概率。\(1\leq k\leq n\leq 20, \sum_ip_i=1\)。
solution
考虑如何求出物品 \(r\) 的答案。我们在这里用集合 \(S\) 表示队列中在 \(r\) 后面的物品，当 \(r\) 不在队列中时将 \(S\) 记为 \(?\)，并始终有 \(r\not\in S\)。因为我们观察到我们很难去维护 \(r\) 前面的物品的顺序和弹出时间，进一步发现这根本没有用，因为我们只关心 \(r\) 的死活，当 \(r\) 后面的元素有 \(k-1\) 个的时候，\(r\) 就死了，与 \(r\) 前面怎么死的没有关系。那么：
- 当 \(S=?\) 时，以 \(p_r\) 概率转移至 \(\varnothing\)，以 \(1-p_r\) 概率转移至 \(?\)。
- 当 \(S\neq ?\) 时，
- 以 \(p_r\) 概率转移至 \(\varnothing\)。
- 以 \(\sum_{i\in S}p_i\) 的概率转移到 \(S\)。
- 对于 \(j\not \in S\)，以 \(p_j\) 的概率转移，若 \(|S|=k-1\) 则转移至 \(?\)，否则转移至 \(S\cup \{j\}\)。
如果最终是状态 \(S\) 的概率是可以计算的，那么记为 \(f_S\)。那么有：
- \(f_?=(1-p_r)f_?+\sum_{|S|=k-1}\sum_{i\not \in S}p_if_S\)。
- \(f_{\varnothing}=p_r(f_?+\sum_{S}f_S)\)。因为所有状态的概率之和理应 \(=1\)，所以 \(f_\varnothing=p_r\)。
- \(f_{S\neq\varnothing}=\sum_{i\in S}p_if_S+[|S|<k-1]\sum_{j\in S}p_jf_{S\setminus\{j\}}\)。
这样看来，因为答案不仅能表示成 \(1-f_?\) 还能表示为 \(\sum_{|S|<k}f_S\)，所以直接根据第三条转移即可。这里可以将\(\sum_{i\in S}p_if_S\) 这一项移动位置使之成为：
\[(1-\sum_{i\in S}p_i)f_{S}=[|S|<k-1]\sum_{j\in S}p_jf_{S\setminus\{j\}},S\neq \varnothing. \]就有
\[f_{S}=\frac{\sum_{j\in S}p_jf_{S\setminus\{j\}}}{1-\sum_{i\in S}p_i},0<|S|<k-1. \]这个东西的计算就很轻易了。
code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define popcount __builtin_popcount
typedef long long LL;
int getbit(int x) { return 1 << x; }
bool conbit(int x, int k) { return getbit(k) & x; }
int lowbit(int x) { return x & -x; }
int n, k;
double p[1 << 20], f[1 << 20];
double solve(int r) {
if (p[1 << r] < 1e-5) return 0;
memset(f, 0, sizeof f);
f[0] = p[1 << r];
// f[0]=p[R]
// f[S] 表示 r 前面的元素是 S，不能包括 r
// f[S]=>f[S] (p[S])
// f[S]=>f[S^J] (p[J],j not in S,j!=r)
// f[S]=>f[0] (p[r])
for (int S = 0; S < 1 << n; S++) {
if (conbit(S, r)) continue;
f[S] /= 1 - p[S];
for (int j = 0; j < n; j++)
if (!conbit(S, j) && j != r) {
int J = 1 << j;
f[S ^ J] += f[S] * p[J];
}
}
double ans = 0;
for (int i = 0; i < 1 << n; i++)
if (popcount(i) < k) ans += f[i];
return ans;
}
int main() {
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%lf", &p[1 << i]);
for (int i = 1; i < 1 << n; i++) p[i] = p[i ^ lowbit(i)] + p[lowbit(i)];
for (int i = 0; i < n; i++) printf("%.10lf%c", solve(i), " \n"[i == n - 1]);
return 0;
}