← 返回题目列表

AtCoder · abc280_g

G. 请使用六角网格 2

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个无限六边形网格,如下所示。

六边形单元表示为 (i,j) 有两个整数 i 和 j.
细胞 (i,j) 与以下六个单元格相邻:

  • (i-1,j-1)
  • (i-1,j)
  • (i,j-1)
  • (i,j+1)
  • (i+1,j)
  • (i+1,j+1)

让我们定义两个单元格之间的距离 X 和 Y 从单元格出发所需的最少移动次数 X 到单元格 Y 通过重复移动到相邻单元格。
例如,单元格之间的距离 (0,0) 和 (1,1) is 1,以及单元格之间的距离 (2,1) 和 (-1,-1) is 3.

你被给予 N 细胞 (X_1,Y_1),\ldots,(X_N,Y_N).
有多少种方式可以从这些中选择一种或多种 N 单元格,使得任意两个所选单元格之间的距离最多为 D?
求计数模数 998244353.

约束

  • 1 \leq N \leq 300
  • -10^9\leq X_i,Y_i \leq 10^9
  • 1\leq D \leq 10^{10}
  • (X_i,Y_i) 成对不同。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N D
X_1 Y_1
\vdots
X_N Y_N

输出

打印答案。


示例输入 1

3 1
0 0
0 1
1 0

示例输出 1

5

所选单元格有五种可能的集合: \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\},和 \{(0,0),(1,0)\}.


示例输入 2

9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

示例输出 2

33

示例输入 3

5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482

示例输出 3

31