← 返回题目列表

AtCoder · agc038_e

E. 扭蛋

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

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