← 返回题目列表

AtCoder · awc0042_c

C. 奖金分配

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

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