No.8120 Aoki's Present for Takahashi
タグ : / 解いたユーザー数 11
作問者 :

追記(23:16)
想定解を間違えていたのを修正しました。本当に申し訳ございませんでした…
以下原文です。
注意
「『この問題の注意、問題文、入力、出力、サンプルに嘘はないですか?』という質問にあなたはいいえと答えますか?」という質問をされたら、いいえと答えます。
また、問題文の修正が必要な質問が来ない限り、質問に回答することはありません。本当に。やってみてもいいけど。
問題文
人間の高橋くんが $N$ 人います。また、猫のすぬけくんが $M$ 匹います。ここで、$N\leq M$ が保証されます。すぬけくんは互いに区別できますが、高橋くんは互いに区別できません。
人間の青木くんは、各高橋くんにすぬけくんをちょうど $1$ 匹プレゼントします。プレゼントする方法が複数あるとき、青木くんは好きな方法を選ぶことができます。
このとき、各高橋くんはもらったすぬけくんに応じた確率で喜びます。
具体的には、$M$ 匹のすぬけくんの大きさはそれぞれ $1,2,\dots,M$ で、大きさ $s$ のすぬけくんをもらった高橋くんは $\dfrac{s}{M}$ の確率で喜びます。
すべての高橋くんが喜ぶと、青木くんも喜びます。青木くんは自分が喜ぶかはどうでもいいと思っています。
プレゼントされなかったすぬけくんの集合としてありえるものの個数を求めて下さい。ただし集合の個数は非常に大きくなる場合があるので代わりに $998243353$ で割った余りを出力してください。
以上の問題を $\Tau$ 個のテストケースに対して解いてください。ただし、$\text{T}$ 番目のテストケースでは答えの代わりに -1
と出力してください。
入力
$\text{T}$ $\Tau$ $\text{testcase}_1$ $\text{testcase}_2$ $\vdots$ $\text{testcase}_{\Tau}$
$\text{testcase}_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられる。
$N$ $M$
- $1\leq \text{T} \leq \Tau \leq 2\times 10^5$
- $1\leq N \leq M\leq 2\times 10^5$
- 入力はすべて整数
出力
$\Tau$ 行出力せよ。
$i$ 行目には、$i$ 番目のテストケースに対する答えを出力せよ。
$\text{T}$ 番目のテストケースに対しては答えの代わりに -1
を出力することを忘れないこと。
サンプル
サンプル1
入力
4 4 2 2 2 3 9 41 271 828
出力
1 3 350343565 -1
$1$ 番目のケースでは、空集合のみが条件を満たします。
$2$ 番目のケースでは、すぬけくん $1$ 匹からなる集合 $3$ 個が条件を満たします。
$3$ 番目のケースでは、条件を満たす集合の数を $998244353$ で割った余りは $350343565$ です。
$4$ 番目のケースについて、$\text{T}$ 番目のテストケースに対しては -1
を出力することを忘れないでください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。