Catwalk BrainF**k

대괄호 문자가 정확히 $2k$개 등장한다고 하자. 그 위치를 고르는 방법은 $\binom{N}{2k}$가지이고, 나머지 위치에는 각각 대괄호가 아닌 문자 $6$개 중 하나를 놓을 수 있다. 선택된 $2k$개의 위치에 올바른 괄호 문자열을 놓는 방법의 수는 카탈란 수

$$\mathrm{Cat}(k)=\frac{1}{k+1}\binom{2k}{k}$$

이다. 따라서 컴파일되는 길이 $N$의 문자열 수를 $A_N$이라 하면

$$A_N=\sum_{k=0}^{\lfloor N/2\rfloor}\binom{N}{2k}\mathrm{Cat}(k)6^{N-2k}$$

이다. 한 테스트 케이스만 처리한다면 이 식을 직접 계산하여 $O(N)$에 해결할 수 있다.

전체 테스트 케이스를 빠르게 처리하기 위해 모든 $A_N$을 선형 시간에 전처리한다. [를 높이를 $1$ 올리는 걸음, ]를 높이를 $1$ 내리는 걸음, 나머지 여섯 문자를 높이를 유지하는 서로 다른 $6$개의 걸음으로 보면, 컴파일되는 문자열은 높이가 음수가 되지 않고 마지막에 $0$으로 돌아오는 가중 Motzkin 경로와 같다.

생성함수를

$$F(x)=\sum_{n\ge 0}A_nx^n$$

이라 하자. 첫 걸음을 기준으로 분해하면

$$F(x)=1+6xF(x)+x^2F(x)^2$$

이고, 따라서

$$F(x)=\frac{1-6x-\sqrt{1-12x+32x^2}}{2x^2}$$

이다. 이를 미분하고 정리하면

$$x(1-12x+32x^2)F'(x)+(2-18x+32x^2)F(x)-2=0$$

을 얻는다. $x^n$의 계수를 비교하면 $n\ge 2$에 대해

$$(n+2)A_n=6(2n+1)A_{n-1}-32(n-1)A_{n-2}$$

이다.

실제로 필요한 값은 확률

$$R_n=\frac{A_n}{8^n}$$

이다. 위 점화식을 $8^n$으로 나누면

$$(n+2)R_n=\frac{3(2n+1)}{4}R_{n-1}-\frac{n-1}{2}R_{n-2}$$

이고, 초깃값은 $R_0=1$, $R_1=\cfrac34$이다.

법 $998\,244\,353$에서 $2$, $4$, 그리고 $2\le n+2\le 100\,002$는 모두 역원을 가진다. 따라서 위 점화식을 그대로 모듈러 연산으로 계산할 수 있다. 입력에서 가장 큰 값을 $M$이라 하면 $R_0,R_1,\ldots,R_M$을 한 번 전처리하고 각 질의에 $R_N$을 출력한다.

시간 복잡도는 $O(M+T)$이고, 공간 복잡도는 $O(M+T)$이다.

또한 원래 확률의 분모는 기약분수로 줄이기 전 $8^N$이므로, 기약분수의 분모 역시 $998\,244\,353$과 서로소이다.

Solution written by GPT5.6