羊肉串 - 题目

给出 $m$ 个模板字符串。对于一个字符串，我们可以把这个字符串切成若干段；如果切完后有 $t$ 段分别和某个模板串相等，那么这种切割方式的价值为 $t$。定义一个字符串的价值为所有切割方式的价值的最大值。

板板想知道，有多少长度为 $2n$ 的数字字符串，满足字符串的前 $n$ 位和后 $n$ 位相等，且价值不超过 $k$。

从标准输入读入数据。

输入的第一行包含三个整数 $n$、$m$、$k$；

接下来 $m$ 行，每行一个数字字符串，表示每个模板串。

输出到标准输出。

输出板板想求的字符串个数模 1,000,000,007。

2 2 0
23
41

4 个不合法的字符串为 23|23、3|23|2、41|41、1|41|4。每个数字中的竖线表示一种价值超过 $0$ 的切割方案。

5 2 3
23
41

子任务一（6 分）：$n\le 5, m\le 10$；

子任务二（9 分）：每个模板串长度为 $1$；

子任务三（18 分）：$n\le 20,m\le 50$；

子任务四（15 分）：$k = 0$；

子任务五（13 分）：$k = 1$；

子任务六（19 分）：$k = 2$；

子任务七（20 分）：无特殊限制。

对于所有数据，$n\le 100$、$m\le 200$、$k\le 3$、每个模板串长度不超过 $5$。

在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 $7$ 个测试点，每个测试点的数据规模限制与对应编号的子任务相同。

注意：预测试数据的评测结果与最终评测结果没有关系。

QOJ.ac