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