← 返回题目列表

AtCoder · arc223_d

D. 实验室手中的卡片的期望

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 A “抽”牌和 B 普通卡。 其中 (A+B)! 这些的排列 A+B 牌,随机统一选择一张,按照从上到下的顺序叠放,形成一副牌。 然后, K 牌从牌堆顶抽取并置于你的手上。 只要你的手牌上至少有一张抽牌,重复以下操作:

  • 从你的手牌中舍弃一张抽卡。弃掉的牌将从你的手牌中移除,并且不会返回牌库。
  • 让 c 是牌组中剩余的牌数。添加 \min(c,2) 张牌从牌库顶移至你的手牌。

求期望的数,取模 998244353,你最后手牌中的牌数。

解决 T 每个输入的测试用例。

模的定义 998244353

在本问题的约束下,可以证明答案是一个有理数,并且当它表示为不可约分数时 \frac{P}{Q},它满足 Q {{}\not\equiv{}} 0 \pmod{998244353}。因此,整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 是唯一确定的。输出这个 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 抽卡并 2 普通卡。 再次执行操作后,手上包含 0 抽牌并 2 普通卡。
对于第二个测试用例,最终手牌大小为 2 如果第一张抽牌是抽牌,并且 1 如果是普通卡。期望值为 \frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3}.