問題一覧 > 通常問題

No.1691 Badugi

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : ansainansain / テスター : ygussanyygussany 👑 NachiaNachia
1 ProblemId : 6496 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-12 18:09:13

問題文


$NM$ 枚のカードがあります。それぞれのカードには色がついており、色の種類は $N$ 種類あります。色ごとに、 $1$ から $M$ までの整数が書かれたカードが $1$ 枚ずつ、合計で $M$ 枚あります。

$NM$ 枚のカードから $K$ 枚を選ぶ方法について、選び方の「スコア」を以下のように定義します。
　・$K$ 枚の中から、同じ色のカードも同じ整数のカードも含まないように選べるカードの枚数の最大値(具体的な例についてはサンプル1も参考にしてください。)

$NM$ 枚のカードの中からスコアが $K-2$ になるような $K$ 枚の選び方が何通りありますか？

ただし、答えは非常に大きくなる可能性があるので、 $998244353$ で割った余りを出力してください。

入力

$N$ $M$ $K$

  • $2 \le N,M \le 5 \times 10^5$
  • $3 \le K \le \min(N,M)+2$
  • 入力は全て整数

出力

スコアが $K-2$ になるような $K$ 枚の選び方の数を $998244353$ で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
4 13 4
出力
96252

$4$ 種類の色を赤,緑,青,黒とします。
例えば(赤1,赤2,青3,青4)のスコアは $2$ です。なのでこれは $96252$ 通りのうちの $1$ つです。
(赤1,緑2,青3,黒4)のスコアは $4$ です。
(赤10,赤11,赤12,赤13)のスコアは $1$ です。
(緑13,青13,青2,赤1)のスコアは $3$ です。

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

$4$ 枚の中から $4$ 枚選ぶ唯一の選び方のスコアは $2$ です。

サンプル3
入力
500000 500000 500002
出力
937941197

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

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