No.1646 Avoid Palindrome
Problem Statement
You are given a string $S$ of length $N$. Each character of $S$ is a lowercase English letter $($ a to z $)$ or ?.
Letting $M$ be the number of ? contained in $S$, there are $26^M$ strings obtainable by replacing every ? in $S$ with a lowercase English letter. Among them, find the number of strings that do not contain a palindrome of $2$ or more characters as a substring, modulo $998244353$.
Input
$N$
$S$
- $1 \leq N \leq 5 \times 10^4$
- $S$ is a string of length $N$ consisting of lowercase English letters (
atoz) or? - $N$ is an integer
Output
Output the answer, followed by a newline.
Sample
Sample 1
Input
4
a??d
Output
552
For example, abcd does not contain a substring of $2$ or more characters that is a palindrome.
On the other hand, adad contains substrings of $2$ or more characters that are palindromes, such as ada and dad.
Sample 2
Input
10
palindrome
Output
1
$S$ may contain no ?.
Also, palindrome does not contain a substring of $2$ or more characters that is a palindrome.
Sample 3
Input
5
aaaaa
Output
0
Sample 4
Input
20
????????????????????
Output
930793552
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂