[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://atcoder.jp/contests/agc038/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 $ での整数表現が定義できることが問題の制約から証明できます。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_0 $ $ B_0 $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $
输出格式
すぬけくんが操作を行う回数の期待値を mod $ 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 $
- 入力される値はすべて整数である。
### Sample Explanation 1
すぬけくんが操作を行う回数の期待値は $ 3 $ です。
### Sample Explanation 2
すぬけくんが操作を行う回数の期待値は $ 132929/7200 $ です。