Manhattan Cafe

题目描述

在 $N$ 维空间中，两个点 $x=(x_1, x_2, \dots, x_N)$ 和 $y = (y_1, y_2, \dots, y_N)$ 之间的曼哈顿距离 $d(x,y)$ 定义为：

如果点 $x=(x_1, x_2, \dots, x_N)$ 的各个分量 $x_1, x_2, \dots, x_N$ 都是整数，则称其为格点。 给定在 $N$ 维空间中的格点 $p=(p_1, p_2, \dots, p_N)$ 和 $q = (q_1, q_2, \dots, q_N)$。
有多少格点 $r$ 满足 $d(p,r) \leq D$ 且 $d(q,r) \leq D$？請輸出計數結果對 $998244353$ 取模的值。

输入格式

输入从标准输入给出，格式如下： $N$ $D$ $p_1$ $p_2$ $\dots$ $p_N$ $q_1$ $q_2$ $\dots$ $q_N$

输出格式

输出答案。

1 5
0
3

8

3 10
2 6 5
2 1 2

632

10 100
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

145428186

提示

$1 \leq N \leq 100$ $0 \leq D \leq 1000$ $-1000 \leq p_i, q_i \leq 1000$ 输入中的所有数值均为整数。当 $N=1$ 时，我们考虑一维空间中的点，即数轴上的点。
有 $8$ 个格点满足条件：$-2,-1,0,1,2,3,4,5$.

标签: AtCoder|abc265F

来源

AtCoder|abc265F