No.1970 Chick Sexer
タグ : / 解いたユーザー数 14
作問者 :
57tggx
/ テスター :
PCTprobability
Problem Statement
At a chick hatchery, $N$ male chicks and $N$ female chicks have been born. A hatchery worker will now arrange all $2N$ chicks in a line. Your job as a chick sexer is to first decide on one integer $x$ ($1 \le x \le 2N$), then choose $x$ consecutive chicks from the line, and finally sell the chosen chicks to a farmer.
However, you may not be able to sell all of the $x$ chosen chicks. The hatchery worker can form a pair by choosing any one male and any one female, and will form as many pairs as possible from among the $x$ chicks you chose and take them away. You can sell to the farmer only the remaining chicks (all male or all female).
The farmer has told you, "I don't care about the sex, but I would like you to sell me $K$ chicks." If chicks of the same sex are not distinguished, there are $\binom{2N}{N}$ ways in total for the hatchery worker to arrange the chicks in a line. Among them, for how many arrangements can you sell $K$ chicks to the farmer by appropriately choosing the integer $x$ and $x$ consecutive chicks?
Since the answer can be very large, find it modulo $998244353$.
Input
$N\ K$
- $N$, $K$ are integers.
- $1 \le N \le 2 \times 10^5$
- $1 \le K \le N$
Output
Output, modulo $998244353$, the number of arrangements among the $\binom{2N}{N}$ arrangements for which it is possible to sell $K$ chicks to the farmer, followed by a newline.
Sample
Sample 1
Input
2 2
Output
4
If the hatchery worker arranges the chicks in the order "male, female, male, female" or "female, male, female, male", then no matter how you choose $x$ consecutive chicks, you can sell at most 1 chick to the farmer. For the remaining 4 arrangements, you can sell 2 chicks to the farmer by choosing consecutive "male, male" or "female, female".
Sample 2
Input
5 1
Output
252
No matter how the hatchery worker arranges the chicks, no pair can be formed if you take $x = 1$.
Sample 3
Input
100 80
Output
286724148
Output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。