P3310 [SDOI2014] Counting Bracket Sequences

Alice and Bob know that a sequence consisting of spaces, left parentheses, and right parentheses is called a bracket sequence. A special type of bracket sequence is called a "legal bracket sequence." It is known that: - The empty string is a legal bracket sequence. - If $S_1$ and $S_2$ are both legal bracket sequences, then $S_1+S_2$ is a legal bracket sequence. - If $S$ is a legal bracket sequence, then $(+S+)$ is a legal bracket sequence. - If $S$ is a legal bracket sequence, then inserting a space at any position in $S$ (including the beginning and the end) yields a legal bracket sequence. Now Alice wants to know: for certain states $s$ and $t$ in a given finite state automaton, how many legal bracket sequences of length $k$ start at $s$ and end at $t$. A finite state automaton is a directed graph $G$ with $n$ nodes, each node representing a state, and there are three categories of outgoing directed edges from each state. For every state, all outgoing edges of the same category point to the same state. The three categories correspond to three symbols: left parenthesis, right parenthesis, and space. We number the states starting from $0$. For the $i$-th state, let $dfa_{i,0/1/2}$ denote the target state of the category representing left parenthesis, right parenthesis, and space, respectively, and let $dfa2_{i,0/1/2}$ denote the number of edges in each category. For a path starting from $s$ and ending at $t$, if it has length $k$ and the sequence of symbols corresponding to the edges on the path forms a legal bracket sequence, we call it "a legal bracket sequence that satisfies $[G,s,t,k]$." Now Alice provides Bob with the automaton $G$ and poses $Q$ queries. For each query, Alice will give $s,t,k$, and she hopes Bob can tell her how many legal bracket sequences satisfy $[G,s,t,k]$. She only needs the answer modulo $47$.

The first line contains an integer $n$ denoting the number of states. Lines $2$ through $n+1$, where the $i$-th of them contains six integers $dfa_{i-1,0},dfa2_{i-1,0},dfa_{i-1,1},dfa2_{i-1,1},dfa_{i-1,2},dfa2_{i-1,2}$, describe the outgoing edges of state $i-1$. The next line contains an integer $q$ denoting the number of queries. Each of the following $q$ lines contains three integers $s,t,k$ describing one query.

Output $q$ lines, each containing one integer, the answer for the corresponding query $\bmod\ 47$.

In the sample explanation, the symbol `_` represents a space. For the first query, the legal bracket sequences of length $3$ are: - `___`, with the number of legal options being $3^3 = 27$. - `_()`, `(_)`, `()_`, each with the number of legal options being $1 \times 2 \times 3 = 6$. Therefore, the total number of options is $27 + 6 \times 3 = 45$. Constraints: For $100\%$ of the testdata, $1 \leq n \leq 2$, $0 \leq dfa_{i,j}, s, t < n$, $0 \leq dfa2_{i,j} < 2^{31}$, $1 \leq k \leq 10^5$. Translated by ChatGPT 5