[AGC038E] Gachapon

题意翻译

有一个随机数生成器,生成 $[0,n-1]$ 之间的整数,其中生成 $i$ 的概率为 $\frac{A_i}{S}$,其中,$S=\sum A_i$。 这个随机数生成器不断生成随机数,当 $\forall i\in[0,n-1]$,$i$ 至少出现了 $B_i$ 次时,停止生成,否则继续生成。 求期望生成随机数的次数,输出答案对 $998244353$ 取模的结果。 $A_i,B_i\geq 1$,$\sum A_i,\sum B_i,n\leq 400$。

题目描述

[problemUrl]: https://agc038.contest.atcoder.jp/tasks/agc038_e すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、 $ 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 $ とします。 また、乱数生成は毎回独立に行われます。 すぬけくんはこれから、次の条件が満たされるまで、乱数生成を繰り返します。 - すべての $ i $ ( $ 0\ \leq\ i\ \leq\ N-1 $ ) について、今までに乱数生成器が $ i $ を生成した回数が $ B_i $ 回以上である。 すぬけくんが操作を行う回数の期待値を求めてください。 ただし、期待値は mod $ 998244353 $ で出力してください。 より正確には、期待値が既約分数 $ P/Q $ で表されるとき、 $ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ <\ 998244353 $ を満たす整数 $ R $ が一意に定まるので、その $ R $ を出力してください。 なお、操作の回数の期待値が有理数として存在し、 さらに mod $ 998244353 $ での整数表現が定義できることが問題の制約から証明できます。 Snuke found a random number generator. It generates an integer between $ 0 $ and $ N-1 $ (inclusive). An integer sequence $ A_0,\ A_1,\ \cdots,\ A_{N-1} $ represents the probability that each of these integers is generated. The integer $ i $ ( $ 0\ \leq\ i\ \leq\ N-1 $ ) is generated with probability $ A_i\ /\ S $ , where $ S\ =\ \sum_{i=0}^{N-1}\ A_i $ . The process of generating an integer is done independently each time the generator is executed. Now, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied: - For every $ i $ ( $ 0\ \leq\ i\ \leq\ N-1 $ ), the integer $ i $ has been generated at least $ B_i $ times so far. Find the expected number of times Snuke will generate an integer, and print it modulo $ 998244353 $ . More formally, represent the expected number of generations as an irreducible fraction $ P/Q $ . Then, there exists a unique integer $ R $ such that $ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ <\ 998244353 $ , so print this $ R $ . From the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo $ 998244353 $ can be defined.

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ A_0 $ $ B_0 $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ ```

输出格式


Print the expected number of times Snuke will generate an integer, modulo $ 998244353 $ .

输入输出样例

输入样例 #1

2
1 1
1 1

输出样例 #1

3

输入样例 #2

3
1 3
2 2
3 1

输出样例 #2

971485877

输入样例 #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

说明

### 制約 - $ 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 $ - 入力される値はすべて整数である。 ### Constraints - $ 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 $ - All values in input are integers. ### Sample Explanation 1 すぬけくんが操作を行う回数の期待値は $ 3 $ です。 ### Sample Explanation 2 すぬけくんが操作を行う回数の期待値は $ 132929/7200 $ です。 ### Sample Explanation 4 The expected number of times Snuke will generate an integer is $ 3 $ . ### Sample Explanation 5 The expected number of times Snuke will generate an integer is $ 132929/7200 $ .