問題一覧 > 通常問題

No.2131 Concon Substrings (COuNt Version)

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 129
作問者 : 👑 AngrySadEight / テスター : 👑 p-adic taiga0629kyopro
お気に入りにしたユーザー ProblemId : 8752 / 自分の提出
問題文最終更新日: 2022-11-26 01:32:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 369 (順位表) の他の問題:

Problem Statement

For a string $T$ consisting of lowercase English letters, define $f(T)$ as the maximum non-negative integer $i$ satisfying the following condition.

There exists a not necessarily contiguous subsequence of $T$ that contains the string con as a contiguous substring exactly $i$ times.

There are $26^N$ possible strings $S$ of length $N$ consisting of lowercase English letters. Find $f(S)$ for all of them and output the sum modulo $998244353$.

Constraints

  • $3 \leq N \leq 3000$
  • $N$ is an integer.

Input

The input is given from standard input in the following format.

$N$

Output

Output the sum of $f(S)$ modulo $998244353$.

Sample

Sample 1
Input
3
Output
1

Among strings of length $3$, considering their not necessarily contiguous subsequences, the strings that can contain $1$ occurrence of con as a contiguous substring number only $1$, namely con, and none can contain $2$ or more. Thus, the answer is $1$.

Sample 2
Input
4
Output
101

Among strings of length $4$, considering their not necessarily contiguous subsequences, the strings that can contain $1$ occurrence of con as a contiguous substring include, for example, corn and cron, and there are $101$ such strings. None can contain $2$ or more, so the answer is $101$.

Sample 3
Input
6
Output
322027

For strings of length $6$, considering their not necessarily contiguous subsequences:

  • There are $322025$ strings that can contain $1$ occurrence of con as a contiguous substring, such as coupon and carbon.
  • There is only $1$ string that can contain $2$ occurrences of con as a contiguous substring, namely concon.
  • There are no strings that can contain $3$ or more occurrences of con as a contiguous substring.

Therefore, the answer is $1 \times 322025 + 2 \times 1 = 322027$.

Sample 4
Input
2021
Output
777297048

Output the sum of $f(S)$ modulo $998244353$.

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