CF698C LRU
题目来源：Codeforces, Codeforces Round #363 (Div. 1), CF698C LRU
题目大意
有一个初始为空的队列，容量为 \(k\)。有 \(n\) 种物品。
接下来会进行 \(10^{100}\) 次操作。每次选择一个物品，物品 \(i\) 有 \(p_i\) 的概率被选中。如果被选中的物品不在队列中，则将它加入队列。此时如果队列长度大于 \(k\)，则弹出“上一次被选中的时间”最早的物品。
问所有操作结束后，每个物品仍在队列中的概率。保留 \(6\) 位小数。
数据范围：\(1\leq k\leq n\leq 20\)，\(0\leq p_i\leq 1\)，\(\sum p_i = 1\)。
本题题解
考虑对每个物品分别求答案。那么有两种情况：
- 操作结束时，队列内不到 \(k\) 种物品。
- 操作结束时，队列内有 \(k\) 种物品（是满的）。
如果 \(p_i \neq 0\) 的物品数 \(< k\)，显然只能是情况 1。因为操作次数极大，而且不发生弹出，所以所有 \(p_i\neq 0\) 的物品答案都是 \(1\)。
否则，在经过了 \(10^{100}\) 次操作后，情况 1 出现的概率可以近似视为 \(0\)。故以下只考虑情况 2。
考虑最终的队列里有哪些物品。发现就是最后加入的 \(k\) 种物品。例如，\(k = 3\)，若操作序列（每次选择的物品）为：\(\dots ,2,2,1,5,1,3,3,4\)，则最终队列里就是：\(\{1,3,4\}\)。
考虑状压 DP。设 \(\text{dp}(s)\) 表示操作序列的一个后缀里，物品集合为 \(s\) 的概率。\(s\) 是一个二进制状压。
转移时，枚举下一个还未在 \(s\) 内出现过的物品，记为物品 \(u\)（其实是操作序列更前面的物品，因为根据状态设计，我们是从后往前 DP 的）。设 \(\text{sum}(s) = \sum_{v\in s}p_v\)。则：
\[\text{dp}(s) = \sum_{u\notin s} (p_u + \text{sum}(s)\cdot p_u + \text{sum}(s)^2\cdot p_u + \dots) \]括号里的式子，表示：【下一次就选中 \(u\) 的概率】 \(+\) 【先选中一个已有的数，再下次才选中 \(u\) 的概率】 \(+\) 【下下下次才选中 \(u\) 的概率】 \(\dots\)。因为操作次数极大，所以有：
\[\begin{align} \text{dp}(s) &= \sum_{u\notin s}\sum_{i = 0}^{\infty} \text{sum}(s)^i \cdot p_u\\ &= \sum_{u\notin s}p_u\cdot \sum_{i = 0}^{\infty} \text{sum}(s)^i\\ &= \sum_{u\notin s}p_u\cdot \frac{1}{1 - \text{sum}(s)} \end{align} \]也可以这样理解上述的转移式：只要选到 \(s\) 里的数，我们就假装无事发生，再选一次。浪费的这一次操作对答案没有影响，因为总操作次数近似无穷大。所以这就等价于，我们强行把 \(s\) 集合里已有的数，被抽到的概率视为 \(0\)。剩下的数概率对应地变为：\(\displaystyle p_u' = \frac{p_u}{\sum_{v\notin s}p_v} = \frac{p_u}{1 - \text{sum}(s)}\)。
于是就可以转移了。
边界是：\(\text{dp}(0) = 1\)。物品 \(i\) 的答案就是 \(\displaystyle \sum_{i\in s, |s| = k}\text{dp}(s)\)。
时间复杂度 \(\mathcal{O}(2^nn)\)。
参考代码
// problem: CF698C
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 20;
int n, K;
int hibit[1 << MAXN], bitcnt[1 << MAXN];
double p[MAXN + 5], sum[1 << MAXN];
double f[1 << MAXN];
int main() {
cin >> n >> K;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cin >> p[i];
cnt += (p[i] != 0);
}
if (cnt < K) {
for (int i = 1; i <= n; ++i) {
cout << (p[i] == 0 ? 0 : 1) << ".00000000" << " \n"[i == n];
}
return 0;
}
for (int i = 1; i <= n; ++i) {
hibit[1 << (i - 1)] = i;
}
for (int i = 1; i < (1 << n); ++i) {
bitcnt[i] = bitcnt[i - (i & (-i))] + 1;
sum[i] = sum[i - (i & (-i))] + p[hibit[i & (-i)]];
}
f[0] = 1;
for (int i = 1; i < (1 << n); ++i) {
if (bitcnt[i] > K)
continue;
for (int _j = i; _j; _j -= (_j & (-_j))) {
int j = hibit[_j & (-_j)];
assert((1 << (j - 1)) == (_j & (-_j)));
if (p[j] == 0)
continue;
f[i] += f[i ^ (1 << (j - 1))] * (p[j] / sum[((1 << n) - 1) ^ i ^ (1 << (j - 1))]);
}
}
cout << setiosflags(ios :: fixed) << setprecision(10);
for (int i = 1; i <= n; ++i) {
/*
double ans = pow(1.0 - p[i], 100000000); // 没出现过
for (int s = 0; s < (1 << n); ++s) {
if (((s >> (i - 1)) & 1) == 0 && bitcnt[s] >= K) {
ans += p[i] / sum[((1 << n) - 1) ^ s] * f[s]; // 出现了但被代替
}
}
ans = 1.0 - ans;
cout << ans << " \n"[i == n];
*/
double ans = 0;
for (int s = 0; s < (1 << n); ++s) {
if (((s >> (i - 1)) & 1) && bitcnt[s] == K) {
ans += f[s];
}
}
cout << ans << " \n"[i == n];
}
return 0;
}