No.1887 K Consecutive Ks (Easy)

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1887 K Consecutive Ks (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 :

miscalc / テスター :

akakimidori 👑

ygussany

1 ProblemId : 7842 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-03-17 19:56:17

問題文

問題 G と同じ問題ですが、制約と実行時間制限が異なります。

$1$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ であって、次の条件を満たすようなものの個数を求めてください。

$A$ には、ある正の整数 $k$ が $k$ 個連続して現れる箇所がある。すなわち、ある正の整数 $i, k$ （ $i + k - 1 \leq N$ ）が存在して、 $A_{i} = A_{i + 1} = \dots = A_{i + k - 1} = k$ を満たす。

答えは非常に大きくなることがあるので、

998244353

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

入力

 $N$   $M$

入力はすべて整数である
$1 \leq N \leq 3000$
$1 \leq M \leq 3000$

出力

条件を満たす $A$ の個数を $998244353$ で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1

入力

2 3

出力

条件を満たす $A$ は以下の $6$ つです。

$(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)$ には、 $1$ が $1$ 個連続して現れる箇所があります。
$(2, 2)$ には、 $2$ が $2$ 個連続して現れる箇所があります。

サンプル2

入力

5 4

出力

条件を満たす $A$ の例を挙げます。

$(4, 2, 4, 1, 3)$ には、 $1$ が $1$ 個連続して現れる箇所があります。
$(4, 3, 3, 3, 2)$ には、 $3$ が $3$ 個連続して現れる箇所があります。
$(2, 2, 4, 2, 2)$ には、 $2$ が $2$ 個連続して現れる箇所があります。
$(2, 2, 3, 3, 3)$ には、 $2$ が $2$ 個連続して現れる箇所、 $3$ が $3$ 個連続して現れる箇所があります。
$(3, 3, 3, 3, 3)$ には、 $3$ が $3$ 個連続して現れる箇所があります。

サンプル3

入力

3000 3000

出力

762730266

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

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

yukicoder

No.1887 K Consecutive Ks (Easy)

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力