Score : $500$ points

问题描述

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

$$\displaystyle d(x,y)=\sum_{i=1}^N \vert x_i - y_i \vert. $$

若点 $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$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

In an $N$-dimensional space, the Manhattan distance $d(x,y)$ between two points $x=(x_1, x_2, \dots, x_N)$ and $y = (y_1, y_2, \dots, y_N)$ is defined by:

$\displaystyle d(x,y)=\sum_{i=1}^n \vert x_i - y_i \vert.$

A point $x=(x_1, x_2, \dots, x_N)$ is said to be a lattice point if the components $x_1, x_2, \dots, x_N$ are all integers.

You are given lattice points $p=(p_1, p_2, \dots, p_N)$ and $q = (q_1, q_2, \dots, q_N)$ in an $N$-dimensional space.
How many lattice points $r$ satisfy $d(p,r) \leq D$ and $d(q,r) \leq D$? Find the count modulo $998244353$.

Constraints

• $1 \leq N \leq 100$
• $0 \leq D \leq 1000$
• $-1000 \leq p_i, q_i \leq 1000$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $D$

$p_1$ $p_2$ $\dots$ $p_N$

$q_1$ $q_2$ $\dots$ $q_N$

Output

Print the answer.

Sample Input 1

1 5
0
3

Sample Output 1

8

When $N=1$, we consider points in a one-dimensional space, that is, on a number line.
$8$ lattice points satisfy the conditions: $-2,-1,0,1,2,3,4,5$.

Sample Input 2

3 10
2 6 5
2 1 2

Sample Output 2

632

Sample Input 3

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

Sample Output 3

145428186

update @ 2024/3/10 11:13:00