CF698C LRU

在构建高负载系统时，缓存策略需要特别关注。本题关于最常用的缓存算法之一——LRU（最近最少使用算法）。 假设缓存最多可以存储 $k$ 个对象。开始时，缓存为空。当某个对象被请求时，我们会检查它是否已经在缓存中，如果不在则将其加入。如果此时缓存中的对象超过 $k$ 个，就需要移除最近最少使用的那个。换句话说，我们移除最后一次被请求时间最早的对象。 现在服务器上存储有 $n$ 个视频，且所有视频大小相同。缓存最多可存储 $k$ 个视频，使用上述缓存算法。我们已知，用户每次访问服务器都会以概率 $p_{i}$ 选择第 $i$ 个视频。视频的选择是独立且无记忆的。 你的任务是：对于每个视频，计算经过 $10^{100}$ 次查询后，它出现在缓存中的概率。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 20$）——视频的数量和缓存的容量。下一行包含 $n$ 个实数 $p_{i}$（$0 \leq p_{i} \leq 1$），每个概率最多保留两位小数。 保证所有 $p_{i}$ 的和等于 $1$。

输出 $n$ 个实数，第 $i$ 个数表示第 $i$ 个视频在 $10^{100}$ 次查询后仍保留在缓存中的概率。若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 即：假设你的答案为 $a$，标准答案为 $b$。若满足 $$ \frac{|a - b|}{\max(1, |b|)} \leq 10^{-6} $$ 则判为正确。

由 ChatGPT 5 翻译