[R68F]求和 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定正整数 $n, m$ 以及两个序列 $a = (a_1, a_2, \ldots, a_n)$ 和 $b = (b_1, b_2, \ldots, b_m)$。

对于任意长度为 $n$ 的序列 $x$ 和长度为 $m$ 的序列 $y$，定义函数 $F(x, y)$ 为：

$$F(x,y) = \sum_{1 \le i_1 < i_2 < \cdots < i_m \le n} \prod_{j=1}^{m} x_{i_j}^{y_j}$$

即 $F(x, y)$ 的计算方式为：在序列 $x$ 中任意挑选一个长度为 $m$ 的子序列 $(x_{i_1}, x_{i_2}, \ldots, x_{i_m})$，将其每一项分别以 $y$ 中对应位置的元素为指数求幂并相乘。$F(x, y)$ 即为所有可能挑选出的子序列贡献之和。

现在，对序列 $a$ 和序列 $b$ 分别进行全排列。设 $a'$ 是 $a$ 的一个排列，$b'$ 是 $b$ 的一个排列。请你计算所有可能的排列组合下 $F(a', b')$ 的总和，即：

$$\sum_{a'} \sum_{b'} F(a', b')$$

由于答案可能很大，请输出其对 $998244353$ 取模后的结果。

对于序列中数值相同的元素，不同下标的元素视为不同的值。例如，若 $a = (2, 2, 3)$，则其全排列共有 $3! = 6$ 种，两个 $2$ 的不同排列位置视为不同的方案。

格式

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示序列 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示序列 $a$。

第三行包含 $m$ 个正整数 $b_1, b_2, \ldots, b_m$，表示序列 $b$。

输出格式

输出一个整数，表示所有排列下 $F(a', b')$ 的总和对 $998244353$ 取模后的结果。

样例

样例输入 #1

3 2
2 3 5
2 1

样例输出 #1

1320

样例输入 #2

2 2
2 3
1 1

样例输出 #2

24

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	其他限制
$1$	$20$	$5$	特殊性质 A
$2$	$20$	$3000$	特殊性质 B
$3$	$20$		特殊性质 C
$4$	$20$	$100$	无
$5$	$20$	$3000$

特殊性质 A ：$m \leq 4$。

特殊性质 B ：$m = 2, b_i = 1$。

特殊性质 C ：$b_i = 1$。

对于 $100\%$ 的数据，$1 \le m \le 10$，$m \le n \le 3000$，$1 \leq a_i, b_i < 998244353$。