D. Xpectation of Cards in Hand with Laboratory

Xpectation of Cards in Hand with Laboratory

AtCoder

⌀ 2281

Xpectation of Cards in Hand with LaboratoryAI (CI翻译)

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.

{"titleZh":"实验室中的手牌卡牌期望","bodyZh":"## 题目描述\n\n有 $A$ 张“抽取”卡和 $B$ 张普通卡。在这 $A+B$ 张卡的 $(A+B)!$ 种排列中，等概率随机选择一种排列，并按照从上到下的顺序叠放卡牌，形成一副牌。然后，从牌堆顶端抽取 $K$ 张卡放入手牌中。只要手牌中至少有一张抽取卡，就重复进行以下操作：\n\n- 从手牌中弃置一张抽取卡。被弃置的卡会从手牌中移除，并且不会回到牌堆中。\n- 令 $c$ 为牌堆中剩余的卡牌数。从牌堆顶端将 $\min(c,2)$ 张卡放入手牌中。\n\n求最终手牌中卡牌数量的期望值，结果对 $998244353$ 取模。\n\n每组输入包含 $T$ 个测试用例，请解决所有测试用例。\n\n $998244353$ 模意义下的定义：在本题约束下，可以证明答案是一个有理数。将其表示为最简分数 $\frac{P}{Q}$ 时，满足 $Q {{}\\not\\equiv{}} 0 \\pmod{998244353}$ 。因此，满足 $R \\times Q \\equiv P \\pmod{998244353}$ 且 $0 \\leq R < 998244353$ 的整数 $R$ 唯一确定。请输出该 $R$ 。\n\n## 约束条件\n\n- $1 \\leq T \\leq 10^5$ \n- $1 \\leq A, B$ \n- $1 \\leq K \\leq A+B \\leq 10^7$ \n- 所有测试用例的 $A+B$ 之和不超过 $10^7$ 。\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入以以下格式给出：\n\n\nT\n\\mathrm{case}_1\n\\mathrm{case}_2\n\\vdots\n\\mathrm{case}_T\n`\n\n每个测试用例 $\u005cmathrm{case}_t$ 的格式如下：\n\n`\nA B K\n\n\n## 输出格式\n\n输出共 $T$ 行答案。第 $t$ 行应包含第 $t$ 个测试用例的答案。"}AI (CI翻译)

样例

Input #1

Output #1

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}$.

题目信息

题号

arc223_d

所属比赛

AtCoder Regular Contest 223

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。