102655: [AtCoder]ABC265 F - Manhattan Cafe

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

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

Input

题意翻译

在 $n$ 维空间内我们定义两个点 $x(x_1,x_2,\ldots,x_n)$,$y(y_1,y_2,\ldots,y_n)$ 的**曼哈顿距离**为 $$d(x,y)=\sum_{i=1}^n|x_i-y_i|$$ 如果一个点 $x$ 的所有坐标均为整数,我们称其为整点。 给出 $n$ 维空间内两个整点 $p,q$ 和一个整数 $D$,求有多少个整点 $r$ 有 $d(p,r)\le D,d(q,r)\le D$。 由于答案可能过大,你需要将答案对 $998244353$ 求余。

Output

分数:500分

问题描述

在一个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)$。
满足$d(p,r) \leq D$和$d(q,r) \leq D$的格点$r$有多少个? 找到答案对$998244353$取模。

约束条件

  • $1 \leq N \leq 100$
  • $0 \leq D \leq 1000$
  • $-1000 \leq p_i, q_i \leq 1000$
  • 输入中的所有值都是整数。

输入

从标准输入以以下格式给出输入:

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

输出

打印答案。


样例输入1

1 5
0
3

样例输出1

8

当$N=1$时,我们考虑一维空间中的点,即数轴上的点。
有8个格点满足条件:$-2,-1,0,1,2,3,4,5$。


样例输入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

加入题单

上一题 下一题 算法标签: