分数: 1600 点
问题陈述
Snuke 发现了一个随机数生成器。 它生成一个介于 0 和 N-1 (含)。 整数序列 A_0, A_1, \cdots, A_{N-1} 表示生成这些整数中的每一个的概率。整数 i (0 \leq i \leq N-1) 是按概率生成的 A_i / S,其中 S = \sum_{i=0}^{N-1} A_i。每次执行生成器时,生成整数的过程都是独立完成的。
现在,Snuke 将使用该生成器重复生成一个整数,直到满足以下条件:
- 对于每个 i (0 \leq i \leq N-1),整数 至少已生成 i 到目前为止 B_i 次。
找到 Snuke 生成整数的预期次数,并将其模数打印出来 998244353。 更正式地说,将预期的代数表示为不可约分数 P/Q。那么,存在唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353,所以打印这个 R.
从这个问题的约束条件来看,我们可以证明期望的世代数是一个有限有理数,其整数表示模 可以定义 998244353 。
约束
- 1 \leq N \leq 400
- 1 \leq A_i
- \sum_{i=0}^{N-1} A_i \leq 400
- 1 \leq B_i
- \sum_{i=0}^{N-1} B_i \leq 400
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_0 B_0
A_1 B_1
\vdots
A_{N-1} B_{N-1}
输出
打印 Snuke 生成整数的预期次数(模数) 998244353.
示例输入 1
2 1 1 1 1
示例输出 1
3
Snuke 生成整数的预期次数为 3.
示例输入 2
3 1 3 2 2 3 1
示例输出 2
971485877
Snuke 生成整数的预期次数为 132929/7200.
示例输入 3
15 29 3 78 69 19 15 82 14 9 120 14 51 3 7 6 14 28 4 13 12 1 5 32 30 49 24 35 23 2 9
示例输出 3
371626143