問題一覧 > 通常問題

No.1646 Avoid Palindrome

レベル : / AI推定難易度 : 1375 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 145
作問者 : 蜜蜂 / テスター : Mitarushi ygussany
お気に入りにしたユーザー ProblemId : 5731 / 自分の提出
問題文最終更新日: 2021-08-05 20:41:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 309 (順位表) の他の問題:

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 ( a to z ) 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もしくは右上の雲マークをクリックしてアカウントを作成してください。