問題一覧 > 通常問題

No.2527 H and W

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 132
作問者 : srjywrdnprkt / テスター : 👑 seekworser
お気に入りにしたユーザー ProblemId : 9236 / 自分の提出
問題文最終更新日: 2023-11-03 21:17:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 411 オムニバスコンテスト (順位表) の他の問題:

Problem Statement

There is a grid of cells with $H$ rows and $W$ columns. Initially, all cells are black.

Consider performing the following operation.

  • Choose some rows (possibly $0$ rows) and some columns (possibly $0$ columns). Then, paint red all cells contained in the chosen rows and all cells contained in the chosen columns.
You are given a positive integer $K$. How many ways are there to choose the rows and columns so that exactly $K$ black cells remain after the operation? Find the count modulo $998244353$.
Here, two ways of choosing are considered different if there is a row or a column that is chosen in only one of them.

Input

$H\ W\ K$

All inputs are integers and satisfy the following constraints.

  • $1\leq H, W \leq 10^6$
  • $1\leq K \leq HW$

Output

Output the number of ways to choose rows and columns satisfying the condition, modulo $998244353$.
Print a newline at the end.

Sample

Sample 1
Input
2 3 2
Output
9

The following $9$ ways satisfy the condition.

  • Column $1$, column $2$
  • Column $1$, column $3$
  • Column $2$, column $3$
  • Row $1$, column $1$
  • Row $1$, column $2$
  • Row $1$, column $3$
  • Row $2$, column $1$
  • Row $2$, column $2$
  • Row $2$, column $3$

Sample 2
Input
5 5 7
Output
0

There may be no way of choosing that satisfies the condition.

Sample 3
Input
1000000 1000000 1000000
Output
894293636

Output the answer modulo $998244353$.

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