AT_abc265_f.[ABC265F] Manhattan Cafe

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

此外，所有坐标分量 $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 5
0
3
```
输出#1
```
8
```
输入#2
```
3 10
2 6 5
2 1 2
```
输出#2
```
632
```

输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页