No.8120 Aoki's Present for Takahashi
タグ : / 解いたユーザー数 12
作問者 :
highlighter
Addendum (23:16)
We have fixed a mistake in the intended solution. We are truly sorry...
The original text follows.
Notes
If asked the question "Would you answer no to the question 'Are there no lies in the notes, problem statement, input, output, and samples of this problem?'?", we will answer no.
Also, we will not answer any questions unless a question requires a correction to the problem statement. Really. You may try, though.
Problem Statement
There are $N$ humans named Takahashi. There are also $M$ cats named Snuke. Here, $N\leq M$ is guaranteed. The Snukes are distinguishable from each other, but the Takahashis are indistinguishable from each other.
A human named Aoki gives exactly $1$ Snuke to each Takahashi as a present. If there are multiple ways to give the presents, Aoki may choose any way he likes.
Then, each Takahashi becomes happy with a probability depending on the Snuke he received.
Specifically, the sizes of the $M$ Snukes are $1,2,\dots,M$ respectively, and a Takahashi who received a Snuke of size $s$ becomes happy with probability $\dfrac{s}{M}$.
If all the Takahashis become happy, Aoki also becomes happy. Aoki does not care whether he becomes happy or not.
Find the number of possible sets of Snukes that were not given as presents. Since the number of sets can be very large, output the remainder when divided by $998243353$ instead.
Solve the above problem for $\Tau$ test cases. However, for the $\text{T}$-th test case, output -1 instead of the answer.
Input
$\text{T}$ $\Tau$
$\text{testcase}_1$
$\text{testcase}_2$
$\vdots$
$\text{testcase}_{\Tau}$
$\text{testcase}_i$ represents the $i$-th test case and is given in the following format.
$N$ $M$
- $1\leq \text{T} \leq \Tau \leq 2\times 10^5$
- $1\leq N \leq M\leq 2\times 10^5$
- All inputs are integers.
Output
Output $\Tau$ lines.
On the $i$-th line, output the answer to the $i$-th test case.
Do not forget to output -1 instead of the answer for the $\text{T}$-th test case.
Sample
Sample 1
Input
4 4 2 2 2 3 9 41 271 828
Output
1 3 350343565 -1
In the $1$-st case, only the empty set satisfies the condition.
In the $2$-nd case, the $3$ sets each consisting of $1$ Snuke satisfy the condition.
In the $3$-rd case, the number of sets satisfying the condition, modulo $998244353$, is $350343565$.
Regarding the $4$-th case, do not forget to output -1 for the $\text{T}$-th test case.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。