No.1691 Badugi
Problem Statement
There are $NM$ cards. Each card has a color, and there are $N$ kinds of colors. For each color, there is one card with each integer from $1$ to $M$ written on it, with $1$ card per integer, for a total of
$M$ cards.
For a way of choosing $K$ cards from the $NM$ cards, the "score" of the choice is defined as follows.
・The maximum number of cards that can be selected from the $K$ cards such that no two selected cards have the same color or the same integer. (See also Sample 1 for concrete examples.)
How many ways are there to choose $K$ cards from the $NM$ cards so that the score is $K-2$ ?
Since the answer can be very large, output it modulo $998244353$.
Input
$N$ $M$ $K$
- $2 \le N,M \le 5 \times 10^5$
- $3 \le K \le \min(N,M)+2$
- All input values are integers.
Output
Output the number of ways to choose $K$ cards so that the score is $K-2$, modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
4 13 4
Output
96252
Let the $4$ colors be red, green, blue, and black.
For example, the score of (red 1, red 2, blue 3, blue 4) is $2$. Therefore, this is $1$ of the $96252$ ways.
The score of (red 1, green 2, blue 3, black 4) is $4$.
The score of (red 10, red 11, red 12, red 13) is $1$.
The score of (green 13, blue 13, blue 2, red 1) is $3$.
Sample 2
Input
2 2 4
Output
1
The only way to choose $4$ cards from the $4$ cards has a score of $2$.
Sample 3
Input
500000 500000 500002
Output
937941197
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ansain
Nachia