/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
ドローカード A 枚と普通のカード B 枚があります。 これら A+B 枚のカードからなる順列は (A+B)! 通りありますが、そのうちの 1 つを一様ランダムに選び、その順番に上下に積み重ねて山札とします。 そして山札の上から K 枚を引き、手札にします。 手札にドローカードが 1 枚以上ある限り、以下の操作を繰り返します。
- 手札にあるドローカードを 1 枚捨てる。捨てたカードは手札からなくなり、山札にも戻らない。
- 山札にあるカードの枚数を c として、山札の上から \min(c,2) 枚のカードを手札に加える。
最終的な手札のカード枚数の期待値を \text{mod } 998244353 で求めてください。
1 つの入力につき、T 個のテストケースを解いてください。
\text{mod } {998244353} の定義
この問題の制約のもとでは、求める答えは有理数であることが証明でき、さらにこれを既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq A,B
- 1 \leq K \leq A+B \leq 10^7
- すべてのテストケースにおける A+B の総和は 10^7 以下
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケース \mathrm{case}_t は以下の形式で与えられる。
A B K
出力
答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。
入力例 1
4 2 2 3 1 2 1 10 20 4 20 10 4
出力例 1
2 332748119 944679050 774829082
1 つ目のテストケースでは、最初の手札にドローカードが必ず 1 枚以上あり、山札にあるカードの枚数は 1 枚です。
操作を 1 回行うと手札にはドローカードが 1 枚と普通のカードが 2 枚あることになります。
もう一度操作を行って手札にはドローカードが 0 枚と普通のカードが 2 枚ある状態になります。
2 つ目のテストケースでは、最初に引くカードがドローカードと普通のカードの場合で最終的な手札の枚数はそれぞれ 2,1 枚となります。期待値は \frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3} です。
Score : 600 points
Problem Statement
There are A "draw" cards and B normal cards. Among the (A+B)! permutations of these A+B cards, one is chosen uniformly at random, and the cards are stacked top to bottom in that order to form a deck. Then, K cards are drawn from the top of the deck and placed in your hand. As long as your hand contains at least one draw card, repeat the following operation:
- Discard one draw card from your hand. The discarded card is removed from your hand and does not return to the deck.
- Let c be the number of cards remaining in the deck. Add \min(c,2) cards from the top of the deck to your hand.
Find the expected number, modulo 998244353, of cards in your final hand.
Solve T test cases per input.
Definition of modulo 998244353
Under the constraints of this problem, it can be proved that the answer is a rational number, and that when it is expressed as an irreducible fraction \frac{P}{Q}, it satisfies Q {{}\not\equiv{}} 0 \pmod{998244353}. Thus, the integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 is uniquely determined. Output this R.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq A, B
- 1 \leq K \leq A+B \leq 10^7
- The sum of A+B over all test cases is at most 10^7.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case \mathrm{case}_t is given in the following format:
A B K
Output
Output the answers over a total of T lines. The t-th line should contain the answer for the t-th test case.
Sample Input 1
4 2 2 3 1 2 1 10 20 4 20 10 4
Sample Output 1
2 332748119 944679050 774829082
For the first test case, the initial hand always contains at least 1 draw card, and the deck has 1 card remaining.
After performing the operation once, the hand contains 1 draw card and 2 normal cards.
After performing the operation once more, the hand contains 0 draw cards and 2 normal cards.
For the second test case, the final hand size is 2 if the first drawn card is a draw card, and 1 if it is a normal card. The expected value is \frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3}.