A6962 | 修复古老的预言
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
考古学家在沙漠遗迹中发现了 $N$ 卷残缺的羊皮纸(编号 $0$ 到 $N-1$)。令人惊讶的是,这 $N$ 卷羊皮纸的长度完全相同,且上面密密麻麻地写满了小写英文字母。
根据考古学家的推测,这些羊皮纸中隐藏着一条**终极预言**(目标字符串 $T$)。
修复这条预言的规则非常特殊:
1. 预言 $T$ 的第 $i$ 个字符必须从这 $N$ 卷羊皮纸中的某一个字符提取。
2. 我们必须**从左到右**依次复原预言的字符。
3. 如果预言的第 $i$ 个字符取自某卷羊皮纸的第 $k$ 列,那么预言的第 $i+1$ 个字符必须取自任意一卷羊皮纸的 **第 $k$ 列之后**(即列下标严格大于 $k$)的位置。
4. 你可以重复使用同一卷羊皮纸,只要遵守上述的“列下标严格递增”规则即可。
请你计算一下,有多少种不同的方案可以从这 $N$ 卷羊皮纸中完整地拼凑出预言 $T$?
由于方案数可能非常巨大,请输出答案对 $10^9 + 7$ 取模后的结果。
根据考古学家的推测,这些羊皮纸中隐藏着一条**终极预言**(目标字符串 $T$)。
修复这条预言的规则非常特殊:
1. 预言 $T$ 的第 $i$ 个字符必须从这 $N$ 卷羊皮纸中的某一个字符提取。
2. 我们必须**从左到右**依次复原预言的字符。
3. 如果预言的第 $i$ 个字符取自某卷羊皮纸的第 $k$ 列,那么预言的第 $i+1$ 个字符必须取自任意一卷羊皮纸的 **第 $k$ 列之后**(即列下标严格大于 $k$)的位置。
4. 你可以重复使用同一卷羊皮纸,只要遵守上述的“列下标严格递增”规则即可。
请你计算一下,有多少种不同的方案可以从这 $N$ 卷羊皮纸中完整地拼凑出预言 $T$?
由于方案数可能非常巨大,请输出答案对 $10^9 + 7$ 取模后的结果。
输入格式
第一行包含两个整数 $N$ 和 $L$,分别表示羊皮纸的数量和每卷羊皮纸的长度。
接下来 $N$ 行,每行包含一个长度为 $L$ 的字符串,表示羊皮纸的内容。
最后一行包含一个字符串 $T$,表示需要复原的预言目标串。
接下来 $N$ 行,每行包含一个长度为 $L$ 的字符串,表示羊皮纸的内容。
最后一行包含一个字符串 $T$,表示需要复原的预言目标串。
输出格式
输出一个整数,表示构造预言的方案数(对 $10^9 + 7$ 取模)。
输入输出样例
输入 #1
3 4 acca bbbb caca aba
输出 #1
6
输入 #2
2 4 abba baab bab
输出 #2
4
## 样例解释与数据范围
### 样例 #1 解释
羊皮纸内容:
- 0:
- 1:
- 2:
目标:
我们可以这样构造(列下标从 0 开始):
1.
2.
3.
4.
5.
6.
共 6 种。
### 数据范围
- $1 \le N \le 1000$ (羊皮纸数量)
- $1 \le L \le 1000$ (羊皮纸长度)
- $1 \le |T| \le 1000$ (目标串长度)
- 所有字符均为小写英文字母。
**数据点分布:**
- 测试点 1-5:$L, |T| \le 10$
- 测试点 6-15:$L, |T| \le 100$
- 测试点 16-25:$L, |T| \le 1000$
### 样例 #1 解释
羊皮纸内容:
- 0:
acca- 1:
bbbb- 2:
caca目标:
aba我们可以这样构造(列下标从 0 开始):
1.
aba -> 第 0 列('a' from 0), 第 1 列('b' from 1), 第 3 列('a' from 0)2.
aba -> 第 0 列('a' from 0), 第 1 列('b' from 1), 第 3 列('a' from 2)3.
aba -> 第 0 列('a' from 0), 第 2 列('b' from 1), 第 3 列('a' from 0)4.
aba -> 第 0 列('a' from 0), 第 2 列('b' from 1), 第 3 列('a' from 2)5.
aba -> 第 1 列('a' from 2), 第 2 列('b' from 1), 第 3 列('a' from 0)6.
aba -> 第 1 列('a' from 2), 第 2 列('b' from 1), 第 3 列('a' from 2)共 6 种。
### 数据范围
- $1 \le N \le 1000$ (羊皮纸数量)
- $1 \le L \le 1000$ (羊皮纸长度)
- $1 \le |T| \le 1000$ (目标串长度)
- 所有字符均为小写英文字母。
**数据点分布:**
- 测试点 1-5:$L, |T| \le 10$
- 测试点 6-15:$L, |T| \le 100$
- 测试点 16-25:$L, |T| \le 1000$
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?