分数: 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}.