← 返回题目列表

AtCoder · abc432_g

G. 二项式之和(A, B)

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

分数: 575 点

问题陈述

给你一个正整数序列 A=(A_1,A_2,\dots,A_N) 长度 N 和正整数序列 B=(B_1,B_2,\dots,B_M) 长度 M.

查找值 \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \binom{A_i}{B_j},模数 998244353.

在这里, \displaystyle \binom{x}{y} 代表选择的方式数 y 对象来自 x 对象(二项式系数),特别是,它是 0 if x < y.

约束

  • 1\leq N,M \leq 5\times 10^5
  • 1\leq A_i,B_j \leq 5\times 10^5
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

输出

输出答案。


示例输入 1

3 2
2 5 4
1 3

示例输出 1

25

答案是 \displaystyle \binom{2}{1}+\binom{2}{3}+\binom{5}{1}+\binom{5}{3}+\binom{4}{1}+\binom{4}{3}=2+0+5+10+4+4=25.


示例输入 2

4 4
2 5 1 5
2 1 2 4

示例输出 2

65

示例输入 3

6 8
203497 47202 407775 394325 463982 304784
468417 302156 131932 235902 395728 78537 223857 330739

示例输出 3

602855848