yijan yyds
by 弦巻こころ @ 2021-03-23 11:56:00
好像只写了翻译错误的第一句话，完整翻译
有 $n$ 种物品和一个大小为 $k$ 的队列，有 $p_i$ 的概率会选择第 $i$ 种物品放入队列，如果队列已经有 $i$ 则将队列中的 $i$ 移到队尾。
如果队列中元素个数超过 $k$ 则弹出队首。
求 $10^{100}$ 次操作后每种物品留在队列的概率。
$n,k \le 20$
```
有 $n$ 种物品和一个大小为 $k$ 的队列，有 $p_i$ 的概率会选择第 $i$ 种物品放入队列，如果队列已经有 $i$ 则将队列中的 $i$ 移到队尾。
如果队列中元素个数超过 $k$ 则弹出队首。
求 $10^{100}$ 次操作后每种物品留在队列的概率。
$n,k \le 20$
```
by yijan @ 2021-03-23 11:58:29
原翻译没错吧，英文题目不是跟原翻译一样吗
by SevenDusk @ 2021-03-23 12:23:47
倒着做是直接把操作序列给reverse过来，进行一个一一映射
但是计算还在集合内的数还是正着考虑的吧
by SevenDusk @ 2021-03-23 12:27:48
@[SevenDusk](/user/118622)
>In other words, we remove the object that has the smallest time of the last query.
也就是说弹出的是最后一个被询问的数，而不是最后一个加入 cache 的。
Least Recently **Used**
by yijan @ 2021-03-23 12:32:43
@[SevenDusk](/user/118622) 但是正着考虑，也就是说你只能算出直到 $k$ 个数的队列填满的时候的停留在里面的概率，感觉上这个东西并不等价于最后 $k$ 个数的概率吧。
by yijan @ 2021-03-23 12:34:39
@[yijan](/user/63398) 这个指的是在不在队列里出现的情况下
by SevenDusk @ 2021-03-23 12:36:49
@[yijan](/user/63398) 是一样的
考虑一个操作序列的概率
$\prod\limits_{i=0}^{lim-1} p_i$
那么到过来就是
$\prod\limits_{i=0}^{lim-1} p_{lim-i-1}$两者是相等的
by SevenDusk @ 2021-03-23 12:39:37
yijan yyds！
by Soulist @ 2021-03-23 14:18:35
@[SevenDusk](/user/118622) 一个序列和它倒过来显然是一一对应的，但是既然你是正着做的，那么为什么要把序列倒过来呢 /yun
by yijan @ 2021-03-23 14:20:50