#CW67. 刷墙墙刷(mirror)
刷墙墙刷(mirror)
题目描述
给定两个长度均为 的字符串,位置从 到 编号:初始字符串 只含小写英文字母,目标模板串 只含小写英文字母和问号 ?。
从字符串 开始,可以进行任意次(也可以一次都不进行)如下操作:选择当前字符串中的一个连续子串,左右端点为 ,满足长度 为奇数且至少为 ;然后把这个子串替换成任意一个同长度的小写字母回文串。区间外的字符保持不变,下一次操作在上一次操作得到的字符串上继续进行。
先把 中的每个 ? 独立替换为一个小写英文字母,得到目标字符串 ; 中原本是字母的位置必须保持该字母。求有多少种这样的 可以由 经过有限次操作得到,答案对 取模。
输入格式
从 mirror.in 文件中读入。
第一行包含整数 ,满足 。
第二行是长度为 的小写字母串 。
第三行是长度为 、只含小写字母和 ? 的字符串 。
输出格式
从 mirror.out 文件中输出。
输出一个整数,表示满足条件的目标字符串 的数量对 取模的结果。
样例 1 输入
5
abcde
?????
样例 1 输出
1318877
样例 2 输入
3
abc
???
样例 2 输出
677
样例 3 输入
5
zzzzz
?cbba
样例 3 输出
1
样例 3 解释
只有一个 ?,候选目标串只有 个,即首字符任取、其余四位固定为 cbba。其中只有 bcbba 可达(它含有长度 的回文 bbb),其余候选串都不含任何长度 的奇数长度回文,且都不是 本身,因此答案为 。
数据范围
所有输入满足 ; 的长度为 且只含小写英文字母; 的长度为 且只含小写英文字母和 ?。模数固定为 。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 10 | ||
| 2 | 且 只含小写字母 | ||
| 3 | 20 | 且 只含 ? |
|
| 4 | |||
| 5 | 40 | 无额外限制, |