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