fstqwq edited 1 年，5 月前
假设操作的 $\{x_1, x_2, \dots, x_k \}$ 给定，我们可以判断是否存在相应的合法操作：对于 $1 \dots n$，我们分别检验每个数是否能被表示出来就可以了。
因此，问题变为了构造一个最小的集合 $\{x_1, x_2, \dots, x_k \}$，使得 $1 \dots n$ 能被表示出来。注意到不选也是一种表示方法来表示 $0$，因此能表示出 $n + 1$ 个数，所以可以立刻得到 $\lceil \log_2(n + 1) \rceil$ 的上下界，构造方法为 $1, 2, 4, \dots, 2 ^ {k - 2}, n - (2 ^ {k-1} - 1)$，其中 $k = \lceil \log_2(n + 1) \rceil$。
假设答案至少为 $r$，且 $a, b$ 已经完成操作，那么我们可以有这样的不等式：
$$ \frac {a} {a + b} \geq r \Rightarrow (1 - r) a - rb \geq 0.$$
因此，给 $a$ 加 $1$，$b$ 减 $1$ 的收益是线性的，因此一定在 $a$ 最大和最小时取到极值，对两者取 $\max$ 即可。
有两种方法思考这道题，但是本质是一致的。
先假设每天都出去玩。这样，如果到某天来不及了，我只能放弃之前某天出去玩，此时显然放弃浪费时间越多的越好。因此，从前到后维护当前还能放弃的时间差最大堆，需要的时候弹掉最大的直到满足条件，最后输出堆的大小。
先假设每天都认真学习，此时可以算出到底给每天争取了多少摸鱼的时间。如果想摸鱼，那影响应该越小越好，因此类似第一个做法反过来，维护需要完成一次摸鱼需要的最小时间；当某天还有空闲时间没有花完的时候，你可以给未来的摸鱼「做准备」。这个过程可以通过线段树或者堆实现。
注意到 $p$ 是字符串的周期，等价于 $|s|-p$ 是字符串的 border：一个长度 $x$ 是 $s$ 的 border，当且仅当 $s$ 中长度为 $x$ 的前缀与后缀相等；KMP 算法维护的就是每个前缀的最长 border 的长度（「前缀后缀最大值」），且在 fail 上进行跳转即是跳到更短的 border 上。
将整个字符串倒过来，将后缀问题转换成前缀问题，使用 KMP 求出每个前缀的 border 总长度和 border 数量，即可计算出此题的解。其中，所有 border 在 fail 指针上跳转可得，维护求和即是在 fail 上进行递推：
$$
\begin{aligned}
\mathrm{cnt}_i = \mathrm{cnt}_{\mathrm{fail}_i} + 1 \\
\mathrm{sum}_i = \mathrm{sum}_{\mathrm{fail}_i} + i
\end{aligned}
$$
注：
1. 还有一些其他的做法。例如，对于每个后缀 $p$，二分出一个最长的长度 $k$，使得 $p$ 是 $s[n-k+1 \dots n]$ 的周期，可以使用哈希或者 Z 算法 (exKMP) 来进行判断。
2. 关于 KMP 和 border，一道与此题原理类似的题是 NOI 2014 动物园，可以参考这个题的思路。
由于下菜时下哪种菜和捞菜都是随机的，实际上 $m$ 种菜可以视为互相独立的。我们先考虑简单版本问题，也即一种菜如何计算；困难版本要求我们 同时 计算所有的菜的可能方案，并对答案求平均。
每次捞菜时，锅里有多少菜是已知的。记 $j$ 时刻捞菜之前锅里的菜有 $\frac 1 {b_j}$ 个；如果 $j$ 时刻没有捞菜的话 $b_j = 0$。每个 $b_i$ 的含义是 不通过存活检定的概率，检定失败会被捞走。由于每次检定是独立的，因此可以使用前缀积或者线段树来查询每次下菜操作在合理的区间内被捞出来的概率，求和即是答案。
对于困难版本问题，直接做 $m$ 次时间上是不可以接受的，因此我们考虑使用卷积。如果对每个 $t$，都计算出恰好煮了 $t$ 秒之后被捞上来的菜的期望数量，我们只需要对这个期望乘上菜在这个时间被捞出是好的的概率，求和即是答案。记期望为 $f_t$，令 $a_i$ 表示 $i$ 时刻是否下了菜（下菜是 $1$，没下菜是 $0$）， $c_j$ 表示 $j$ 时刻是否捞了菜。如果一个下菜时间 $i$ 下的菜恰好在时间 $j$ 被捞走，意味着在期间每次捞菜时都不能选到它，并且 $j$ 时刻恰好又选中了它。
$$ f_t = \sum_{j - i = t} c_j \frac{a_i}{b_j} \prod_{i < k < j} \left( 1 - b_k \right) .$$
后面的连乘可以用一个前缀积维护，记前缀积为 $p_i$，则
$$ f_t = \sum_{j - i = t} c_j \frac{a_i p_{j - 1} b_j}{p_i}.$$
后面的式子要么只和 $i$ 有关，要么只和 $j$ 有关，而 $j - i$ 又是定值 $t$，因此把项分离之后做卷积即可。此时有一个小问题，如果某次捞菜时锅中只有一个菜，那显然必定捞上这个菜，式子里的 $1 - \frac 1 {b_k}$ 就会是 $0$，乘法不可逆会导致前缀积失效。因此，每个锅里没菜的时段都应当断开，把分成的若干段做完之后最后加起来即可。
复杂度 $O(n \log n + m)$。