P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2

原题链接：。

给定 $n$ 个字符串 $S_1, \ldots, S_n$ 以及一个字符串 $T$。 对于一个字符串 $R$，定义 $|R|$ 表示 $R$ 的长度、$R_{[l,r]}$ 表示 $R$ 的第 $l\sim r$ 个字符组成的字符串。字符串 $R'$ 是字符串 $R$ 的前缀当且仅当存在 $1\leq p\leq |R|$ 且 $p$ 为整数使得 $R'=R_{[1,p]}$。 定义一个字符串 $R$ 是**好的**当且仅当它是某个 $S_i$ 的前缀**或** $R$ **为空**。 对于若干字符串 $R_1,R_2,\dots,R_k$，定义 $R_1+R_2+\dots+R_k$ 为 $R_1,R_2,\dots,R_k$ 顺次拼接得到的字符串。 定义一个三元组 $(l,r,k)$（$l,r,k$ 均为整数）是好的当且仅当 $1\leq l\leq r\leq|T|$，$1\leq k\leq K$ 且存在 $k$ 个**好的**字符串 $R_1,R_2,\dots,R_k$ 使得 $R_1+R_2+\dots+R_k=T_{[l,r]}$。 请你求出好的三元组的数量，并对于每个 $i$ 求出有多少好的三元组 $(l,r,k)$ 满足 $l\leq i\leq r$。如果你只能求出两者中其一，也可以获得部分分数，见【**输出格式**】。

第一行，三个非负整数 $id,n,K$，其中 $id$ 表示测试点编号（所有样例满足 $id=0$），$n$ 表示字符串数量，$K$ 表示对好的三元组的限制。 接下来 $n$ 行，每行一个字符串 $S_i$。 接下来一行，一个字符串 $T$。

第一行，一个非负整数，表示好的三元组的数量。 第二行，$\lvert T\rvert$ 个非负整数，第 $i$ 个表示满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量。 本题使用**自定义校验器**进行评分，对于每个测试点： * 如果你的程序正确地求出了好的三元组的数量并正确地对于每个 $1\leq i\leq |T|$ 求出了满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量，你可以获得该测试点 $100\%$ 的分数。 * 如果你的程序未能正确地求出了好的三元组的数量但正确地对于每个 $1\leq i\leq |T|$ 求出了满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量，你可以获得该测试点 $80\%$ 的分数。 * 如果你的程序正确地求出了好的三元组的数量但未能正确地对于每个 $1\leq i\leq |T|$ 求出了满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量，你可以获得该测试点 $60\%$ 的分数。 * 否则，你不能获得该测试点的任何分数。 注意，即使你希望获得某测试点 $80\%$ 或 $60\%$ 的分数，你也需要在第一行输出一个数并在第二行输出 $\lvert T\rvert$ 个数。

**【样例解释 #1】** 符合要求的 $(l,r,k)$ 有以下 $13$ 组： * $(1,1,1)$； * $(1,1,2)$； * $(1,2,1)$； * $(1,2,2)$； * $(1,3,2)$； * $(3,3,1)$； * $(3,3,2)$； * $(3,4,2)$； * $(3,5,2)$； * $(4,4,1)$； * $(4,4,2)$； * $(4,5,1)$； * $(4,5,2)$。 **【样例 #4】** 见附件中的 `string/string4.in` 与 `string/string4.ans`。 该组样例满足测试点 $1\sim3$ 的约束条件。 **【样例 #5】** 见附件中的 `string/string5.in` 与 `string/string5.ans`。 该组样例满足测试点 $4\sim6$ 的约束条件。 **【样例 #6】** 见附件中的 `string/string6.in` 与 `string/string6.ans`。 该组样例满足测试点 $7\sim10$ 的约束条件。 **【样例 #7】** 见附件中的 `string/string7.in` 与 `string/string7.ans`。 该组样例满足测试点 $13\sim14$ 和测试点 $16\sim17$ 的约束条件。 **【样例 #8】** 见附件中的 `string/string8.in` 与 `string/string8.ans`。 该组样例满足测试点 $18\sim20$ 的约束条件。 **【数据范围】** 对于所有测试数据，保证：$1\leq n\leq10$，$1\leq |S_i|\leq5\times10^4$，$1\leq |T|,K\leq5\times10^5$，字符串仅包含小写英文字母 $\texttt{a}\sim\texttt{z}$。 | 测试点编号 | $n\leq$ | $\lvert S_i\rvert\leq$ | $\lvert T\rvert\leq$ | $K\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:|:--:|:--:| | $1\sim3$ | $10$ | $50$ | $50$ | $50$ | 无 | | $4\sim6$ | $10$ | $100$ | $300$ | $300$ | 无 | | $7\sim10$ | $10$ | $1000$ | $5000$ | $5000$ | 无 | | $11\sim12$ | $10$ | $5\times10^4$ | $5\times10^5$ | $1$ | 无 | | $13\sim14$ | $10$ | $5\times10^4$ | $5\times10^5$ | $10$ | 无 | | $15$ | $10$ | $5\times10^4$ | $5\times10^5$ | $5\times10^5$ | 所有字符均为 $\texttt{a}$ | | $16\sim17$ | $10$ | $5\times10^4$ | $5\times10^5$ | $5\times10^5$ | 所有字符在 $\{\texttt{a},\texttt{b}\}$ 中独立均匀随机生成 | | $18\sim20$ | $10$ | $5\times10^4$ | $5\times10^5$ | $5\times10^5$ | 无 |