分数: 500 点
问题陈述
给出的是序列 N 整数: A = (A_1, \dots, A_N) 和 B = (B_1, \dots, B_N)。查找非空子集的数量 S of \{1,2,\ldots,N\} 满足以下条件:
- \max_{i \in S} A_i \geq \sum_{i \in S} B_i.
由于计数可能很大,因此将其模数打印出来 998244353.
约束
- 1 \leq N \leq 5000
- 1 \leq A_i,B_i \leq 5000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
打印子集的数量 S 满足问题陈述中的条件,模 998244353.
示例输入 1
2 3 1 1 2
示例输出 1
2
\{1,2,\ldots,N\} 具有三个子集: \{1\}, \{2\},和 \{1,2\}.
- 对于 S=\{1\},我们有 \max_{i \in S} A_i=3 和 \sum_{i \in S} B_i=1.
- 对于 S=\{2\},我们有 \max_{i \in S} A_i=1 和 \sum_{i \in S} B_i=2.
- 对于 S=\{1,2\},我们有 \max_{i \in S} A_i=3 和 \sum_{i \in S} B_i=3.
因此,条件 \max_{i \in S} A_i \geq \sum_{i \in S} B_i 由两个子集满足: \{1\} 和 \{1,2\}.
示例输入 2
2 1 1 2 2
示例输出 2
0
可能没有满足条件的子集。
示例输入 3
20 1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247 4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017
示例输出 3
476