AT_abc301_f [ABC301F] Anti-DDoS

题目描述

我们将满足以下两个条件的、由英文字母大写和小写字母组成的长度为 $4$ 的字符串称为 DDoS 型字符串：

• 第 $1$、$2$、$4$ 个字符为英文字母大写，第 $3$ 个字符为英文字母小写。
• 第 $1$、$2$ 个字符相同。

例如，DDoS、AAaA 是 DDoS 型字符串，而 ddos、IPoE 不是 DDoS 型字符串。

给定一个由英文字母大写、小写字母以及 ? 组成的字符串 $S$。将 $S$ 中的每个 ? 独立地替换为任意一个英文字母大写或小写字母后，可以得到 $52^q$ 种不同的字符串，其中 $q$ 是 $S$ 中 ? 的个数。在这些字符串中，不包含任何 DDoS 型字符串作为子序列的字符串有多少个？请将答案对 $998244353$ 取模后输出。

输入格式

输入为一行，包含一个字符串 $S$。

输出格式

输出一个整数，表示满足条件的字符串个数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

DD??S

输出 #1

676

输入输出样例 #2

输入 #2

????????????????????????????????????????

输出 #2

858572093

输入输出样例 #3

输入 #3

?D??S

输出 #3

136604

说明/提示

注释

字符串的子序列是指，从字符串中删除 $0$ 个或多个字符后，按原顺序连接剩下的字符所得的字符串。例如，AC 是 ABC 的子序列，而 RE 不是 ECR 的子序列。

约束

• $S$ 仅包含英文字母大写、小写字母和 ?。
• $S$ 的长度满足 $4 \leq |S| \leq 3 \times 10^5$。

样例解释 1

当两个 ? 中至少有一个被替换为小写字母时，必然包含 DDoS 型字符串作为子序列。

样例解释 2

请将答案对 $998244353$ 取模后输出。

由 ChatGPT 4.1 翻译