#CW67. 刷墙墙刷(mirror)

刷墙墙刷(mirror)

题目描述

给定两个长度均为 nn 的字符串,位置从 11 到 nn 编号:初始字符串 aa 只含小写英文字母,目标模板串 bb 只含小写英文字母和问号 ?。

从字符串 aa 开始,可以进行任意次(也可以一次都不进行)如下操作:选择当前字符串中的一个连续子串,左右端点为 l,rl,r,满足长度 r−l+1r-l+1 为奇数且至少为 33;然后把这个子串替换成任意一个同长度的小写字母回文串。区间外的字符保持不变,下一次操作在上一次操作得到的字符串上继续进行。

先把 bb 中的每个 ? 独立替换为一个小写英文字母,得到目标字符串 tt;bb 中原本是字母的位置必须保持该字母。求有多少种这样的 tt 可以由 aa 经过有限次操作得到,答案对 998244353998244353 取模。

输入格式

从 mirror.in 文件中读入。

第一行包含整数 nn,满足 1≤n≤1061\le n\le 10^6。

第二行是长度为 nn 的小写字母串 aa。

第三行是长度为 nn、只含小写字母和 ? 的字符串 bb。

输出格式

从 mirror.out 文件中输出。

输出一个整数,表示满足条件的目标字符串 tt 的数量对 998244353998244353 取模的结果。

样例 1 输入

5
abcde
?????

样例 1 输出

1318877

样例 2 输入

3
abc
???

样例 2 输出

677

样例 3 输入

5
zzzzz
?cbba

样例 3 输出

1

样例 3 解释

bb 只有一个 ?,候选目标串只有 2626 个,即首字符任取、其余四位固定为 cbba。其中只有 bcbba 可达(它含有长度 33 的回文 bbb),其余候选串都不含任何长度 ≥3\ge 3 的奇数长度回文,且都不是 a=zzzzza=zzzzz 本身,因此答案为 11。

数据范围

所有输入满足 1≤n≤1061\le n\le 10^6;aa 的长度为 nn 且只含小写英文字母;bb 的长度为 nn 且只含小写英文字母和 ?。模数固定为 998244353998244353。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 10 1∼21\sim 2 n≤5n\le 5
2 3∼43\sim 4 n≤105n\le 10^5 且 bb 只含小写字母
3 20 5∼85\sim 8 n≤105n\le 10^5 且 bb 只含 ?
4 9∼129\sim 12 n≤2×103n\le 2\times 10^3
5 40 13∼2013\sim 20 无额外限制,n≤106n\le 10^6