問題一覧 > 通常問題

No.2131 Concon Substrings (COuNt Version)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : AngrySadEightAngrySadEight / テスター : taiga0629kyoprotaiga0629kyopro p-adicp-adic
3 ProblemId : 8752 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-26 01:32:40

問題文

英小文字からなる文字列 $T$ について,次のような条件を満たす非負整数 $i$ の最大値を $f(T)$ と定義します.

$T$ の連続とは限らない部分列であって,文字列 con連続する部分列として含む個数が $i$ であるものが存在する.

長さ $N$ の英小文字からなる文字列 $S$ として考えられるものは $26^N$ 個ありますが,その全てに対して $f(S)$ を求め,その総和を $998244353$ で割った余りを出力してください.

制約

  • $3 \leq N \leq 3000$
  • $N$ は整数である.

入力

入力は以下の形式で標準入力から与えられる.

$N$

出力

$f(S)$ の総和を $998244353$ で割った余りを出力せよ.

サンプル

サンプル1
入力
3
出力
1

長さ $3$ の文字列であって,その連続とは限らない部分列を考えたときに,連続する部分列 con を $1$ つ含むようなものがありうるものは con の $1$ 個しかなく,$2$ つ以上含むようなものはありません.よって,答えは $1$ です.

サンプル2
入力
4
出力
101

長さ $4$ の文字列で,その連続とは限らない部分列を考えたときに,連続する部分列 con を $1$ つ含むようなものがありうるものは,例えば corncron などがあり,そのような文字列は $101$ 個あります.$2$ つ以上含むようなものは無いので,答えは $101$ です.

サンプル3
入力
6
出力
322027

長さ $6$ の文字列について,その連続とは限らない部分列を考えたときに,

  • 連続する部分列 con を $1$ つ含むようなものがありうるものは,couponcarbon など, $322025$ 個あります.
  • 連続する部分列 con を $2$ つ含むようなものがありうるものは,concon の $1$ 個のみです.
  • 連続する部分列 con を $3$ つ以上含むようなものはありません.

したがって,答えは $1 \times 322025 + 2 \times 1 = 322027$ となります.

サンプル4
入力
2021
出力
777297048

$f(S)$ の総和を $998244353$ で割った余りを出力してください.

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