#P18642. Expanded Hull

Expanded Hull

Expanded Hull

题目描述

给定整数 N,KN,K,以及三维空间中的 NN 个点

(X1,Y1,Z1),…,(XN,YN,ZN)。(X_1,Y_1,Z_1),\ldots,(X_N,Y_N,Z_N)。

将每个点的三个坐标都乘以 KK,得到

(KX1,KY1,KZ1),…,(KXN,KYN,KZN)。(KX_1,KY_1,KZ_1),\ldots,(KX_N,KY_N,KZ_N)。

设这些新点的凸包为 VV。请计算位于 VV 的内部或边界上、且三个坐标均为整数的点的数量,对 998244353998244353 取模。

输入格式

N K
X_1 Y_1 Z_1
...
X_N Y_N Z_N

输入仅包含一组数据,所有数均为整数。

输出格式

输出一个整数,表示所求点数对 998244353998244353 取模后的结果。

数据范围

  • 4≤N≤1004\le N\le100。
  • 1≤K≤10151\le K\le10^{15}。
  • −200≤Xi,Yi,Zi≤200-200\le X_i,Y_i,Z_i\le200。
  • 给出的 NN 个点两两不同。
  • 不存在一个平面经过所有给出的点,即这些点不全共面。

样例输入 1

4 2
0 0 0
1 0 0
0 1 0
0 0 1

样例输出 1

10

样例输入 2

4 10000
0 0 0
1 0 0
0 1 0
0 0 1

样例输出 2

59878050

样例输入 3

8 314159265358979
5 -3 -3
-5 -3 -3
0 5 -3
0 0 10
4 2 6
-4 2 6
0 -5 6
0 0 -5

样例输出 3

152811018

样例说明

第一组样例中,满足条件的10个整数点为 (0,0,0)(0,0,0)、(1,0,0)(1,0,0)、(2,0,0)(2,0,0)、(0,1,0)(0,1,0)、(1,1,0)(1,1,0)、 (0,2,0)(0,2,0)、(0,0,1)(0,0,1)、(1,0,1)(1,0,1)、(0,1,1)(0,1,1)、(0,0,2)(0,0,2)。