Cats & Soup: Magic Recipe

Merge whenever possible

Assign weight $2^{x-1}$ to a level-$x$ item. A merge preserves total weight of each type and frees one slot. Repeated merging leaves at most one item at each level below $M$. This normalized representation is uniquely determined by binary carries and uses the fewest slots among representations with the same weight.

Fix an entire sequence of generated types. Whenever another strategy can continue generating along this sequence, the fully normalized strategy can also continue, since it has at least as much free space. As soon as total star weight reaches $2^{L-1}$, merging can create a level-$L$ star. Thus immediate merging is no worse for every possible sequence of outcomes. We may normalize after every generation and generate again whenever a slot remains.

DP states

Let $S=2^{L-1}$ and $H=2^{M-1}$. Before success, normalized stars are represented by a mask $$. Moons below level are represented by a mask . Each level- moon permanently occupies a slot.

Let $c$ be the number of slots left after excluding those permanent moons, and let $F(c,s,t)$ be the success probability. The number of occupied remaining slots is $\operatorname{popcount}(s)+\operatorname{popcount}(t)$. If it is at least , no new item can be generated and the value is zero. Initialize the layer to zero.

A generated star increments $s$, automatically performing all binary carries. Reaching $S$ is immediate success. A generated moon increments $t$; reaching $H$ creates a permanent moon, resetting $t$ to zero and decreasing $c$.

With $\alpha=a/b$ and $\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}$$

The answer is $F(N,0,0)$. A transition that creates the target succeeds even if it uses the last free slot. A maximum-level moon cannot be discarded and must reduce $c$.

Process $c$ in increasing order and $s,t$ in decreasing order. Only the current and previous capacity layers are needed. Time is $O(N2^{L+M-2})$ and space is $O({}^{}$, with at most state evaluations under the full limits.

Subtasks

For subtask 1, memoize a vector containing the actual number of items of every type and level. Perform an available merge, or branch into the two generated types when no merge remains and space is available. There are at most $\binom{N+2M}{2M}$ count vectors, at most $84$ in this subtask. This is the supplied naive implementation.

For subtask 2, $L=1$, so the first generated star wins. If every generated item is a moon, the inventory first gets stuck after

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

generations. The answer is $1-\beta^D$, computed in $O(\log998\,244\,353+\log D)$ time including the inverse.

Modular arithmetic

Let $P=998\,244\,353$. Compute $\alpha=a b^{P-2}\bmod P$ and . Every generation increases total weight by one, and inventory weight is at most , so only finitely many generations are possible. The reduced denominator divides a power of and is invertible because .

Each sum of two probability products is below $2(P-1)^2<2\cdot10^{18}$, so signed 64-bit arithmetic suffices. The exact reduced fraction need not be constructed.

The independent forward reference propagates probability mass by total star and moon weight. For small cases, verification also compared every merge and generation action using exact rational optimal-policy search.

Solution written by GPT