103015: [Atcoder]ABC301 F - Anti-DDoS
Description
Score : $500$ points
Problem Statement
A DDoS-type string is a string of length $4$ consisting of uppercase and lowercase English letters satisfying both of the following conditions.
- The first, second, and fourth characters are uppercase English letters, and the third character is a lowercase English letter.
- The first and second characters are equal.
For instance, DDoS and AAaA are DDoS-type strings, while neither ddos nor IPoE is.
You are given a string $S$ consisting of uppercase and lowercase English letters and ?.
Let $q$ be the number of occurrences of ? in $S$. There are $52^q$ strings that can be obtained by independently replacing each ? in $S$ with an uppercase or lowercase English letter.
Among these strings, find the number of ones that do not contain a DDoS-type string as a subsequence, modulo $998244353$.
Notes
A subsequence of a string is a string obtained by removing zero or more characters from the string and concatenating the remaining characters without changing the order.
For instance, AC is a subsequence of ABC, while RE is not a subsequence of ECR.
Constraints
- $S$ consists of uppercase English letters, lowercase English letters, and
?. - The length of $S$ is between $4$ and $3\times 10^5$, inclusive.
Input
The input is given from Standard Input in the following format:
$S$
Output
Print the answer.
Sample Input 1
DD??S
Sample Output 1
676
When at least one of the ?s is replaced with a lowercase English letter, the resulting string will contain a DDoS-type string as a subsequence.
Sample Input 2
????????????????????????????????????????
Sample Output 2
858572093
Find the count modulo $998244353$.
Sample Input 3
?D??S
Sample Output 3
136604
Input
题意翻译
- 定义形如 `DDoS` 的序列为类 DDoS 序列，其中 `DD` 表示两个相同的任意大写字母，`o` 表示任意小写字母，`S` 表示任意大写字母。 - 给定一个由大小写字母和 `?` 组成的序列 $S$，问有多少种将 `?` 替换为大小写字母的方案可以使 $S$ 不含有任何一个类 DDoS 子序列，答案对 $998244353$ 取模。 - $4 \le \left|S\right| \le 3 \times 10^5$Output
问题描述
一个DDoS类型字符串是一个长度为$4$的字符串，包含大写和小写英文字母，满足以下两个条件。
- 第一个、第二个和第四个字符是大写英文字母，第三个字符是小写英文字母。
- 第一个和第二个字符相等。
例如，DDoS和AAaA是DDoS类型字符串，而ddos和IPoE则不是。
给你一个由大写和小写英文字母以及?组成的字符串$S$。设$S$中?的数量为$q$。通过独立地将$S$中的每个?替换为大写或小写英文字母，可以得到$52^q$个字符串。在这些字符串中，找到不包含DDoS类型字符串作为子序列的字符串数量，对$998244353$取模。
注释
一个字符串的子序列是从该字符串中删除零个或多个字符，然后不改变剩余字符的顺序而连接起来的字符串。
例如，AC是ABC的子序列，而RE不是ECR的子序列。
约束
- $S$由大写英文字母、小写英文字母和
?组成。 - $S$的长度在$4$和$3\times 10^5$之间，包括边界值。
输入
输入数据从标准输入给出，格式如下：
$S$
输出
打印答案。
样例输入1
DD??S
样例输出1
676
当至少一个?被替换为小写英文字母时，得到的字符串将包含一个DDoS类型字符串作为子序列。
样例输入2
????????????????????????????????????????
样例输出2
858572093
对结果取模$998244353$。
样例输入3
?D??S
样例输出3
136604