[SDOI2014]括号序列计数

题目描述

Alice和Bob知道,一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为”合法括号序列“。已经知道: (1)”()“是合法的括号序列,空串是合法的括号序列。 (2)如果S1是合法的括号序列,S2是合法的括号序列,则S1与S2拼接起来的序列S1+S2也是合法的括号序列。 (3)如果S是合法的括号序列,在其左右分别插入一个左括号和一个右括号所得到的字符串”(“+S1+”)“也是合法的括号序列。 (4)如果S是合法的括号序列,在S的任何位置(包括头尾位置)插入一个空格,得到的序列也是合法的括号序列。 现在,Alice希望知道:对于某个已知的有限状态自动机中的状态s与t,存在多少以s为起点,t为终点的长度为k的合法括号序列。所谓有限状态自动机,又可以被认为是一个有向图G,由n个结点组成,每一个结点表示一个状态,且存在三类以此为起点出去的有向边,对于每一个状态(或结点)来说其出去的同一类有向边将指向同样的状态(或结点)。三类有向边分别代表三种符号:左括号”(“,右括号”)“和空格。这里,我们将状态(或结点)从0开始编号。 对于第i个状态,用dfa[i][0],dfa[i][1],dfa[i][2]分别表示从i出发,代表了左括号、右括号和空格的那一类边指向的状态(或结点),再用dfa2[i][0],dfa2[i][1],dfa2[i][2]表示每一类边的个数。对于一条从s出发到t结束的路径,满足长度为k且路径经过的边对应的符号组成了一组合法的括号匹配,则称作”满足[G,s,t,k]的合法括号序列“。 现在,Alice为Bob提供了自动机G,并提出Q组询问。对于每一组询问,Alice会给出s、t和k,她希望Bob可以告诉她满足[G,s,t,k]的合法括号序列有多少组。她只需要知道答案除以47后的余数。

输入输出格式

输入格式


第一行一个整数n,表示状态数(或结点数)。 之后n行,对于其中的第i行,有6个32位整数,依次为dfa[i-1][0],dfa2[i-1][0],dfa[i-1][1],dfa2[i-1][1],dfa[i-1][2],dfa2[i-1][2]。 之后一行有一个整数Q,表示Alice的询问次数。 之后Q行,每一行有3个32位的整数,依次为s,t,k。

输出格式


输出文件有Q行。其中第i行对应了第i个询问,只有一个整数,表示满足[G,s,t,k]的合法括号序列的个数,答案只需要除以47后的余数。

输入输出样例

输入样例 #1

1
0 1 0 2 0 3
6
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8

输出样例 #1

45
9
10
2
19
25

说明

样例说明: 对于第一组询问,长度为3的合法括号序列依次有: (1)三个空格,则在自动机中的合法方案数为:3\*3\*3=27。 (2)对于`( )`、`() `和` ()`,则在自动机中的合法方案数为:1\*3\*2=6。 所以总的可行方案数为:27+3\*6=27+18=45。 对于100%的数据,n <= 2,k <= 100000,Q <= 10。