問題一覧 > 通常問題

No.1646 Avoid Palindrome

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

問題文

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

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

入力

N
S

  • 1≤N≤5×104
  • S は英小文字( a ～ z )もしくは ? からなる長さ N の文字列
  • N は整数

出力

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

サンプル

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

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

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

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

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

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

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

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