問題一覧 > 通常問題

No.2131 Concon Substrings (COuNt Version)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 123
作問者 : 👑 AngrySadEightAngrySadEight / テスター : 👑 p-adicp-adic taiga0629kyoprotaiga0629kyopro
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$ つ含むようなものがありうるものは，例えば corn や cron などがあり，そのような文字列は $101$ 個あります．$2$ つ以上含むようなものは無いので，答えは $101$ です．

サンプル3
入力
6
出力
322027

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

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

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

サンプル4
入力
2021
出力
777297048

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

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