AT_abc265_f [ABC265F] Manhattan Cafe

题目描述

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

此外，所有坐标分量 $x_1, x_2, \dots, x_N$ 都是整数的点 $x=(x_1, x_2, \dots, x_N)$ 被称为格点。

现在给定 $N$ 维空间中的两个格点 $p=(p_1, p_2, \dots, p_N)$ 和 $q=(q_1, q_2, \dots, q_N)$。
请计算满足 $d(p, r) \leq D$ 且 $d(q, r) \leq D$ 的所有可能格点 $r$ 的个数。请将答案对 $998244353$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$N$ $D$ $p_1$ $p_2$ $\dots$ $p_N$ $q_1$ $q_2$ $\dots$ $q_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

1 5
0
3

输出 #1

8

输入输出样例 #2

输入 #2

3 10
2 6 5
2 1 2

输出 #2

632

输入输出样例 #3

输入 #3

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

输出 #3

145428186

说明/提示

限制条件

• $1 \leq N \leq 100$
• $0 \leq D \leq 1000$
• $-1000 \leq p_i, q_i \leq 1000$
• 输入的所有值均为整数

样例解释 1

当 $N=1$ 时，是关于一维空间（即数轴）上的点的问题。满足条件的点有 $-2, -1, 0, 1, 2, 3, 4, 5$ 共 $8$ 个。

由 ChatGPT 4.1 翻译