分数: 366 分
问题陈述
在高桥担任社长的公司里,有 N 员工,每个人都分配了一个编号 1 to N。该公司在一段时间内支付奖金 D 个月。
每位员工 i (1 \leq i \leq N) 有一个正整数 P_i 代表他们的“贡献级别”,总贡献为 S = P_1 + P_2 + \cdots + P_N.
每个月 j (1 \leq j \leq D),公司奖金总额为 W_j。该基金按照每位员工缴费水平的比例进行分配。也就是说,员工的奖金金额 i 月份收到 j is
\frac{P_i \times W_j}{S}
之后 D 月份已结束,员工收到的奖金总额 i is
T_i = \frac{P_i}{S} \times \sum_{j=1}^{D} W_j
Aoki 作为会计经理,想要计算 产品 两个闭包的 所有员工奖金总额:
R = \prod_{i=1}^{N} T_i
R 是一个非负有理数。快递 R 作为不可约分数 \frac{A}{B} (A \geq 0, B > 0, \gcd(A, B) = 1)。特别是,当 R = 0,让 A = 0 和 B = 1.
计算 A \times B^{-1} \bmod 998244353,其中 B^{-1} 表示模逆 B 模数 998244353.
保证在这个问题的约束下, B 与 998244353,意味着模逆始终存在。
约束
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^6
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq W_j \leq 10^9 (1 \leq j \leq D)
- S = P_1 + P_2 + \cdots + P_N 不是以下的倍数 998244353.
- 所有输入值均为整数。
输入
N D P_1 P_2 \cdots P_N W_1 W_2 \cdots W_D
- 第一行包含员工人数 N 和月数 D,用空格分隔。
- 第二行包含贡献级别 P_1, P_2, \ldots, P_N ,用空格分隔。
- 第三行包含奖金资金 W_1, W_2, \ldots, W_D 表示每个月,以空格分隔。
输出
输出值 A \times B^{-1} \bmod 998244353,其中 R 表示为不可约分数 \frac{A}{B},作为单个整数 0 (含)和 998244353 (独家)一行。
样本输入 1
2 2 1 1 2 2
示例输出 1
4
示例输入 2
3 3 1 2 3 0 0 0
示例输出 2
0
示例输入 3
5 4 1 2 3 4 5 10 20 30 40
示例输出 3
211088321
示例输入 4
10 10 3 7 2 5 11 4 8 6 9 1 100 200 150 300 50 175 225 125 275 80
示例输出 4
953616835
示例输入 5
1 1 1 5
示例输出 5
5