← 返回比赛

已结束 GESP巅峰赛#29

← 上一题下一题 →

A7092 | $星塔抄卷$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

星塔的抄卷师要把一段古老经文誊写到卷轴上。经文中有些字迹模糊，用 ? 标注。誊写完成后的文本必须避免“连三同音”的失礼： 对任意相邻的长度为 $3$ 的子串，三个字符必须两两不同。 给定原始串 $s$（长度为 $n$），你可以把每个 ? 独立替换为某个大写字母。问有多少种替换方式，使得得到的新串 $t$ 满足：对一切 $i$（$1\le i\le n-2$），都有 $$ t_i\ne t_{i+1},\quad t_i\ne t_{i+2},\quad t_{i+1}\ne t_{i+2}. $$ 将答案对 $998244353$ 取模。若 $n<3$，上述约束不生效，任意替换皆可。

输入格式

- 第一行：整数 $n$ - 第二行：字符串 $s$

输出格式

- 一行一个整数，表示方案数模 $998244353$ 的结果。

输入输出样例

输入 #1

3
?A?

输出 #1

输入 #2

2
??

输出 #2

输入 #3

3
AAA

输出 #3

- $1\le n\le 2\times 10^5$ 测试点分层 测试点$n$ 范围$1\sim 2$$1\le n\le 200$$3\sim 6$$200< n\le 5\times 10^3$$7\sim 20$$5\times 10^3< n\le 2\times 10^5$

C++ 编辑器

输入

输出