#P3605. [Sdoi2014]括号序列计数

    ID: 2812 传统题 2000ms 512MiB 尝试: 39 已通过: 12 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划计数 DP自动机 DP线性代数与代数矩阵乘法多项式与生成函数卷积转化离线与分治CDQ 分治分治 FFTNTTCF2700

[Sdoi2014]括号序列计数

[SDOI2014] 括号序列计数

题目描述

Alice 和 Bob 知道,一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为合法括号序列。已知:

  • 空串是合法括号序列;
  • 如果 S1S_1 和 S2S_2 均是合法括号序列,则 S1+S2S_1+S_2 是合法括号序列;
  • 如果 SS 是合法括号序列,则在 SS 左右分别加一个左括号和右括号所得序列也是合法括号序列;
  • 如果 SS 是合法括号序列,在 SS 的任何位置(包括头尾位置)插入一个空格得到的序列是合法括号序列。

现在 Alice 希望知道:对于某个已知的有限状态自动机中的状态 ss 与 tt ,存在多少以 ss 为起点、tt 为终点、长度为 kk 的合法括号序列。

有限状态自动机是一个有向图 GG,由 nn 个结点组成,每一个结点表示一个状态,且存在三类以此为起点的有向边。对于每一个状态,其向外的同一类有向边指向同样的状态。三类有向边分别代表三种符号:左括号、右括号和空格。

我们将状态从 00 开始编号。对于第 ii 个状态,用 $\mathrm{dfa}_{i,0},\mathrm{dfa}_{i,1},\mathrm{dfa}_{i,2}$ 分别表示从 ii 出发,代表了左括号、右括号和空格的那一类边指向的状态,再用 $\mathrm{dfa2}_{i,0},\mathrm{dfa2}_{i,1},\mathrm{dfa2}_{i,2}$ 表示每一类边的个数。对于一条从 ss 出发到 tt 结束的路径,满足长度为 kk 且路径经过的边对应的符号构成的序列组成了一组合法的括号匹配,则这条路径计作一种满足 [G,s,t,k][G,s,t,k] 的方案。若两条路径选择的边不同,即使那些边的符号完全相同也分别计数。

现在,Alice 为 Bob 提供了自动机 GG,并提出 QQ 组询问。对于每一组询问,Alice 会给出 s,t,ks,t,k,她希望 Bob 可以告诉她满足 [G,s,t,k][G,s,t,k] 的合法括号序列有多少组。她只需要知道答案除以 4747 后的余数。

输入格式

第一行一个整数 nn 表示状态数,第二到 n+1n+1 行,第 ii 行六个整数 $dfa_{i-1,0},dfa2_{i-1,0},dfa_{i-1,1},dfa2_{i-1,1},dfa_{i-1,2},dfa2_{i-1,2}$,描述第 i−1i-1 个状态的出边。

接下来一行一个整数 qq 表示询问数,接下来 qq 行每行三个整数 s,t,ks,t,k 描述一组询问。

输出格式

输出 qq 行,每行一个整数表示对应询问的答案  mod  47\bmod\ 47 的结果。

样例

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
45
9
10
2
19
25

样例解释

在样例解释中使用符号 _ 代表空格。

对于第一组询问长度为 33 的合法括号序列有:

  • ___,合法方案数为 33=273^3 = 27;
  • _()、(_)、()_,合法方案数均为 1×2×3=61\times2\times3=6。

所以总方案数为 27+6×3=4527+6\times3=45。

数据范围

对于所有数据,1≤n≤21 \leq n \leq 2,0≤dfai,j,s,t<n0 \leq dfa_{i,j} , s , t < n,0≤dfa2i,j<2310 \leq dfa2_{i,j} < 2^{31},1≤k≤1051 \leq k \leq 10^5。