Cats & Soup: Magic Recipe

能合并就立即合并

定义 $x$ 级物品的重量为 $2^{x-1}$。合并保持每种物品的总重量不变，并空出一个格子。不断合并后，低于 $M$ 级的每个等级最多剩一个物品。这是由二进制进位唯一确定的规范状态，并在总重量相同的所有表示中占用最少的格子。

固定完整的生成种类序列。如果某个策略能按照这个序列继续生成，规范化策略也能继续，因为空格不会更少。当星星总重量达到 $2^{L-1}$ 时，通过合并必定能获得 $L$ 级星星。因此，对每一种生成结果序列，立即合并都不会更差。只需每次生成后合并到底，然后在有空格时继续生成。

状态与转移

令 $S=2^{L-1}$、$H=2^{M-1}$。成功之前，星星可用 $0$ 的掩码表示，低于 级的月亮可用 的掩码表示。每个 级月亮永久占据一个格子。

令 $c$ 为扣除这些永久月亮后剩余的格子数，$F(c,s,t)$ 为从该状态出发的成功概率。若 $\operatorname{popcount}(s)+\operatorname{popcount}(t)\geq c$，则无法继续生成，概率为零。 的整层初始化为零。

生成星星等价于 $s$ 加一，并自动处理所有二进制进位；达到 $S$ 就立即成功。生成月亮等价于 $t$ 加一；达到 $H$ 时生成一个永久月亮，令 $t=0$、$c$ 减一。

设 $\alpha=a/b$、$\beta=1-\alpha$，有

$$F(c,s,t)=\alpha A+\beta B,$$ $$A=\begin{cases}1&s+1=S,\\F(c,s+1,t)&s+1<S,\end{cases}$$ $$B=\begin{cases}F(c-1,s,0)&t+1=H,\\F(c,s,t+1)&t+1<H.\end{cases}$$

答案为 $F(N,0,0)$。即使占用了最后一个空格，只要产生目标星星就应判定成功。最高级月亮不能丢弃，必须减少可用容量。

按 $c$ 递增、同层内 $s,t$ 递减的顺序计算，只保留当前层和上一层。时间复杂度为 $O(N2^{L+M-2})$，空间复杂度为 $O(2^{L+}$。完整限制下最多计算 个状态。

子任务

子任务 1 可记录每种物品每个等级的实际数量并记忆化搜索。有可合并的物品就执行合并，否则在有空格时按两种生成结果分支。数量向量至多有 $\binom{N+2M}{2M}$ 个，在本子任务中至多为 $84$。所附 naive 即采用此方法。

子任务 2 中 $L=1$，首次生成星星即成功。如果一直生成月亮，首次无法继续时的生成次数为

$$D=\begin{cases}2^N-1&N<M,\\(N-M+2)2^{M-1}-1&N\geq M.\end{cases}$$

答案为 $1-\beta^D$。包括逆元计算在内，复杂度为 $O(\log998\,244\,353+\log D)$。

令 $P=998\,244\,353$，用 $\alpha=a b^{P-2}\bmod P$、 计算。每次生成使总重量增加一，总重量最多为 ，因此生成次数有限。最简分母是 的某次幂的约数，由 可知逆元存在。

两个概率乘积的和小于 $2(P-1)^2<2\cdot10^{18}$，有符号 $64$ 位整数足够，无需构造完整的最简分数。独立的 forward 程序按星星和月亮总重量向前传播概率；小规模验证还使用精确有理数比较了所有合并和生成选择。

Solution written by GPT