問題一覧 > 通常問題

No.3391 Line up Dominoes

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : yu23578 / テスター : GaLLium yt142857 aa36 Germanium32
ProblemId : 12780 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-11-28 22:03:27
コンテストの他の問題:

問題文

yu23578君は、 $1$ から $N$ までの番号が振られた $N$ 種類のドミノをそれぞれ $10^{100}$ 個ずつ持っています。ドミノ $i$ の大きさは $A_i$ です。

yu23578君は、この中から $M$ 個のドミノを選んで横一列に並べることにしました。以下の条件を満たすドミノの置き方の総数を $\mathrm{mod} 998244353$ で解答してください。

  • 隣り合うドミノの大きさの差は $K$ 以下である。

制約

  • $1 \le N,M \le 10^4$
  • $0 \le K \le 10^9$
  • $1 \le A_i \le 10^9$
  • 入力はすべて整数

入力

$N\ M\ K$
$A_1\ A_2\ A_3\ \cdots\ A_N$

出力

条件を満たすドミノの置き方の総数を $\mathrm{mod} 998244353$ で解答してください

最後に改行してください。

サンプル

サンプル1
入力
3 2 2
3 1 4
出力
7

条件を満たす並べ方は、

(ドミノ $1,$ ドミノ $1$ )
(ドミノ $1,$ ドミノ $2$ )
(ドミノ $1,$ ドミノ $3$ )
(ドミノ $2,$ ドミノ $1$ )
(ドミノ $2,$ ドミノ $2$ )
(ドミノ $3,$ ドミノ $2$ )
(ドミノ $3,$ ドミノ $3$ )

の $7$ 通りなので、 $7$ を出力してください。

サンプル2
入力
1 1 1000000000
1000000000
出力
1

サンプル3
入力
2 357 82
35 78
出力
782487810

$\mathrm{mod} 998244353$ で解答してください

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