← 返回题目列表

AtCoder · ttpc2022_n

N. 扩展船体

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

配点 : 500 点

問題文

整数 K 和 按字典顺序比较 3 在维度为 N 点 (x_1,y_1,z_1), \dots, (x_N,y_N,z_N) 。 对于

N 点 (K x_1,K y_1,K z_1), \dots, (K x_N,K y_N,K z_N) 的凸包内部或边界内,且坐标均为整数的点的数量为 998244353 后求余数。

制約

  • 所有输入均为整数
  • 4 \leq N \leq 100
  • 1 \leq K \leq 10^{15}
  • \sout{-2 \times 10^3 \leq x_i,y_i,z_i \leq 2 \times 10^3} (1 ≤ i ≤ N)
  • \color{red}-2 \times 10^2 \leq x_i,y_i,z_i \leq 2 \times 10^2 (1 ≤ i ≤ N)
  • (x_i,y_i,z_i) \neq (x_j,y_j,z_j) (1 ≤ i < j ≤ N)
  • N 没有平面可以经过所有

入力

输入是按以下格式从标准输入给出的。

N K
x_1 y_1 z_1
\vdots
x_N y_N z_N

出力

打印答案。 来自


入力例 1

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

出力例 1

10

4 点 (0,0,0),(2,0,0),(0,2,0),(0,0,2) 凸包内部和边界上坐标为整数的点。 (0,0,0),(1,0,0),(2,0,0),(0,1,0),(1,1,0),(0,2,0),(0,0,1),(1,0,1),(0,1,1),(0,0,2) 可以得到第 10 件。


入力例 2

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

出力例 2

59878050

4 点 (0,0,0),(10000,0,0),(0,10000,0),(0,0,10000) 凸包内包含坐标为整数的点为 166\,766\,685\,001 个,因此得到 998244353 余数除以 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