Cats & Soup: Magic Recipe

합칠 수 있으면 바로 합친다

레벨 $x$인 아이템의 무게를 $2^{x-1}$이라 하자. 합치는 행동은 종류별 총무게를 유지하고, 차지하는 칸을 하나 줄인다. 같은 종류의 아이템을 더 이상 합칠 수 없을 때까지 합치면, 레벨 $M$ 미만에서는 각 레벨의 아이템이 최대 하나만 남는다. 이 상태는 총무게의 이진 표현으로 유일하게 정해지며, 같은 총무게를 표현하는 상태 중 칸을 가장 적게 사용한다.

생성될 종류의 순서를 미리 고정해 보자. 어떤 전략이 그 순서대로 생성을 계속할 수 있다면, 매번 가능한 합성을 모두 하는 전략도 계속할 수 있다. 같은 총무게에서 빈 칸이 더 적어지지 않기 때문이다. 별의 총무게가 $2^{L-1}$에 도달하면 합성을 통해 반드시 레벨 $L$의 별을 만들 수 있다. 따라서 모든 생성 결과의 순서에 대해 즉시 합성하는 전략이 다른 전략보다 불리하지 않다. 목표를 만들 때까지 가능한 합성을 모두 한 뒤, 빈 칸이 있으면 생성하면 된다.

상태

$S=2^{L-1}$, $H=2^{M-1}$이라 하자. 목표 별이 생기기 전에는 별의 정규화된 상태를 $$인 비트마스크로 나타낼 수 있다. 달은 레벨 미만의 비트마스크 와, 합칠 수 없는 레벨 달의 개수로 나타낸다.

레벨 $M$ 달이 차지하는 칸을 뺀 나머지 칸 수를 $c$라 하자. $F(c,s,t)$를 이 상태에서 목표를 달성할 확률로 정의한다. 현재 남은 칸 중 사용한 칸 수는

$$\operatorname{popcount}(s)+\operatorname{popcount}(t)$$

이다. 이 값이 $c$ 이상이면 더 생성할 수 없으므로 확률은 $0$이다. $c=0$인 상태도 $0$으로 둔다.

빈 칸이 있으면 별 생성 시 $s$에 $1$을 더한다. 이는 합성으로 생기는 모든 이진 올림을 한꺼번에 처리한다. $s+1=S$이면 즉시 목표를 달성한다. 달 생성 시에도 $t$에 $1$을 더하되, $$이면 레벨 달이 하나 생겨 , 이 된다.

$\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)$이다. 목표 별이 만들어지는 전이는 인벤토리가 가득 찼는지 검사하기 전에 성공으로 처리해야 한다. 레벨 $M$ 달은 버릴 수 없으며, 반드시 $c$를 줄여야 한다.

$c$는 증가하는 순서로, 같은 $c$에서는 $s,t$를 감소하는 순서로 계산한다. 필요한 값은 같은 층과 바로 이전 층에만 있으므로 두 층만 저장한다. 시간 복잡도는 $O(N2^{L+M-2})$, 공간 복잡도는 이다. 전체 제한에서 상태 계산은 최대 번이다.

부분 점수

서브태스크 1은 각 종류와 레벨의 실제 개수를 배열로 저장하는 메모이제이션 탐색으로 해결할 수 있다. 가능한 합성을 하나 수행하고 재귀 호출하거나, 합성할 수 없고 빈 칸이 있으면 두 생성 결과로 분기한다. 아이템 수가 $N$ 이하인 개수 배열은 최대 $\binom{N+2M}{2M}$개이며, 이 서브태스크에서는 최대 $84$개다. 제공한 naive가 이 방법이다.

서브태스크 2는 $L=1$이다. 별이 한 번이라도 생성되면 성공하므로, 달만 계속 생성했을 때 인벤토리가 처음 막힐 때까지의 생성 횟수 $D$를 구하면 된다.

$$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}$이므로 signed 64-bit 정수로 충분하다. 기약분수 자체를 큰 정수로 계산할 필요는 없다.

독립 검증용 forward 풀이는 별과 달의 총무게를 사용하여 확률 질량을 앞으로 전파한다. 작은 경우에는 생성과 모든 합성 선택을 전부 비교하는 유리수 최적 정책 탐색도 수행했다.

Solution written by GPT