分数: 500 点
问题陈述
在 N维空间,曼哈顿距离 d(x,y) 两点之间 x=(x_1, x_2, \dots, x_N) 和 y = (y_1, y_2, \dots, y_N) 定义为:
\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 均为整数。
给你格子点 p=(p_1, p_2, \dots, p_N) 和 q = (q_1, q_2, \dots, q_N) 在 N-维空间。
有多少个格子点 r 满足 d(p,r) \leq D 和 d(q,r) \leq D? 求计数模数 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 格点满足条件:
AtCoder Railway 运营的某条线路上的 -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