No.1646 Avoid Palindrome
タグ : / 解いたユーザー数 133
作問者 : 蜜蜂 / テスター : Mitarushi 👑 ygussany
問題文
長さ $N$ の文字列 $S$ が与えられます。 $S$ の各文字は英小文字 $($ a
~ z
$)$ もしくは ?
です。
$S$ の ?
を全て英小文字に置き換えてできる文字列は $S$ の含む ?
の数を $M$ として $26^M$ 通りありますが、そのうち $2$ 文字以上の回文を連続部分文字列として含まないものの個数を $998244353$ で割った余りを求めてください。
入力
$N$
$S$
- $1 \leq N \leq 5 \times 10^4$
- $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もしくは右上の雲マークをクリックしてアカウントを作成してください。