問題一覧 > 通常問題

No.1431 東大文系数学2020第2問改

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 15
作問者 : 👑 evimaevima / テスター : mine691mine691
1 ProblemId : 5995 / 出題時の順位表
問題文最終更新日: 2021-03-14 12:07:47

問題文

座標平面上に $2N$ 本の直線 $x = a\ (a = 1, \ldots, N),\ y = b\ (b = 1, \ldots, N)$ がある。
以下,$N^2$ 個の点 $(a, b)\ (a = 1, \ldots, N,\ b = 1, \ldots, N)$ から異なる $M$ 個の点を選ぶことを考える。

次の条件を満たす $M$ 個の点の選び方は何通りあるか。
 上の $2N$ 本の直線のうち,選んだ点を $1$ 個も含まないものがちょうど $K$ 本ある。

この選び方の数を $998244353$ で割った余りを出力するプログラムを提出せよ。

入力

$N\ M\ K$

  • $1 \leqq N \leqq 3000$
  • $1 \leqq M \leqq N^2$
  • $0 \leqq K \leqq 2N - 2$
  • $N, M, K$ は整数

出力

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

サンプル

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

条件は,$x, y$ 座標のいずれかが等しい $2$ 個の点を選ぶ場合に満たされる。

サンプル2
入力
4 5 2
出力
1824

サンプル3
入力
4 5 0
出力
432

サンプル4
入力
3000 1000000 2021
出力
817273302

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