問題一覧 > 通常問題

No.1646 Avoid Palindrome

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 116
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi 👑 ygussanyygussany
6 ProblemId : 5731 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-05 20:41:21

問題文

長さ $N$ の文字列 $S$ が与えられます。 $S$ の各文字は英小文字 $($ az $)$ もしくは ? です。

$S$ の ? を全て英小文字に置き換えてできる文字列は $S$ の含む ? の数を $M$ として $26^M$ 通りありますが、そのうち $2$ 文字以上の回文を連続部分文字列として含まないものの個数を $998244353$ で割った余りを求めてください。

入力

$N$
$S$

  • $1 \leq N \leq 5 \times 10^4$
  • $S$ は英小文字( az )もしくは ? からなる長さ $N$ の文字列
  • $N$ は整数

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4
a??d
出力
552

例えば、 abcd は回文であるような $2$ 文字以上の連続部分文字列を含みません。
また、 adadadadad など、回文であるような $2$ 文字以上の連続部分文字列を含みます。

サンプル2
入力
10
palindrome
出力
1

$S$ が ? を含まないこともあります。
また、 palindrome は回文であるような $2$ 文字以上の連続部分文字列を含みません。

サンプル3
入力
5
aaaaa
出力
0

サンプル4
入力
20
????????????????????
出力
930793552

$998244353$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。