問題一覧 > 通常問題

No.1414 東大文系数学2021第2問改

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : evimaevima / テスター : 37zigen37zigen iaNTUiaNTU
4 ProblemId : 5926 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-14 11:33:03

問題文

$N, M, K$ を与えられた整数とする。$1$ 以上 $N$ 以下の整数から,相異なる $M$ 個の整数を選ぶ。
選んだ数の集合を $S$ とし,$S$ に関する以下の条件を考える。

 条件:$S$ は連続する $K$ 個の整数からなる集合を少なくとも $1$ つ含む。

ただし,$2$ 以上の整数 $k$ に対して,連続する $k$ 個の整数からなる集合とは,ある整数 $l$ を用いて $\{l, l + 1, \cdots\cdots, l + k - 1\}$ と表される集合を指す。
例えば $\{1, 2, 3, 5, 7, 8, 9, 10\}$ は連続する $3$ 個の整数からなる集合 $\{1, 2, 3\}, \{7, 8, 9\}, \{8, 9, 10\}$ を含む。

条件を満たすような選び方は何通りあるか。この選び方の数を $998244353$ で割った余りを解答ファイルに出力せよ。

入力

$N\ M\ K$

  • $2 \leqq K \leqq M \leqq N \leqq 10^7$
  • $N, M, K$ は整数

出力

答えを出力し,末尾で改行せよ。

サンプル

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

条件を満たすような選び方は,$\{1, 2\}, \{2, 3\}, \{3, 4\}$ の $3$ 通りである。

サンプル2
入力
10 5 3
出力
126

サンプル3
入力
10000000 5000000 2021
出力
107056641

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