问题 4835 --4.线性递推

4835: 4.线性递推

题目描述

  有 $10^9$ 个字符串,第 $i$ 个字符串记作 $s_i$
给定整数 $m$ 以及前 $m$ 个字符串 $s_1 \sim s_m$,同时给定一个 $1 \sim m$ 的排列 $a_1 \sim a_m$
那么对于 $i>m$,有下列递推关系式成立:
$s_i = s_{i - m - 1 + a_1} + s_{i - m - 1 + a_2} + \cdots + s_{i - m - 1 + a_m}$
其中字符串的 $+$  运算表示字符串的按顺序拼接。
共有 $q$ 次询问,每次询问给定一个模式串 $t$ 和一个正整数 $n$,请求出模式串 $t$ 作为 $s_n$ 的子串的出现次数,对 $10^9+7$ 取模。

输入

第一行包含一个整数 $m$,表示开始字符串的个数(排列长度)。
接下来 $m$ 行,每行一个字符串,表示前 $m$ 个字符串,保证字符串的长度均相同。
接下来一行,包含 $m$ 个正整数,表示排列 $a$

接下来一行,包含一个整数 $q$,表示询问次数。
对于每一次询问,包含一个字符串和一个整数,分别表示 $T$$n$

输出

输出总共 $q$ 行,每一个询问对应一个答案。

样例输入输出

输入#1 复制
3
ab
ac
ca
2 3 1
3
ac 2
b 1
a 5
输出#1 复制
1
1
5

提示

样例解释
前三个字符串 $\texttt{ab},\texttt{ac},\texttt{ca}$ 。排列为$2,3,1$ 。
第四个字符串为 $\texttt{ac}+\texttt{ca}+\texttt{ab}=\texttt{accaab}$。
第五个字符串为 $\texttt{ca}+\texttt{accaab}+\texttt{ac}=\texttt{caaccaabac}$ 。
记 $L$ 为前 $m$ 个字符串的最大长度。
对于 $10\%$ 的数据,$ m \leq 2 , L \leq 6 , n \leq 10$ ;
对于 $20\%$ 的数据,$ m \leq 2 , L \leq 6 , n \leq 400$ ;
对于 $30\%$ 的数据,$ m \leq 5 , L \leq 50 , n \leq 2\times 10^4$ ;
对于 $50\%$ 的数据,$ m \leq 5 , L \leq 50 , n \leq 10^6$ ;
对于 $80\%$ 的数据,$ m \leq 5 , L \leq 50 , n \leq 10^7$ ;
对于 $100\%$ 的数据,$1\leq m \leq 9, 1 \leq L \leq 200, 1 \leq n \leq 10^9 , 1 \leq |T| \leq L, 1 \leq q \leq 7$。

序号 标题 作者 发表时间 费用 订购数 操作