← 返回题目列表

AtCoder · KeioPC2025_d

D. 我可以全部按下吗?

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

配点 : 100 点

問題文

M 维度空间上的点是 给出了 N 。i 第二点是 位于 (x_{i,1},x_{i,2},\dots,x_{i,M}) 。另外,一个非负整数 还给出了 D 。

\lbrace 1,2,\dots,N \rbrace 的一组子集 在 (S_1,S_2) 中,计算满足以下所有条件的项目数。 满足 998244353 求余数。

  • 1 \le i \le N 的整数 仅包含 i 是 仅由 S_1,S_2 之一。
  • a,b \in S_c 满足的不论的 a,b,c ,\sum_{i=1}^{M} |x_{a,i} - x_{b,i}| \le D 很满意。 您将获得

T 测试用例,因此请解决每个测试用例。

制約

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • 1 \le M \le 4
  • 0 \le D \le 10^9
  • 0 \le x_{i,j} \le 10^9
  • 在所有测试用例中 N 的总和是 2 \times 10^5 以下
  • 所有输入均为整数

入力

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

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出。 打印

N M D
x_{1,1}\ x_{1,2}\ \dots\ x_{1,M}
x_{2,1}\ x_{2,2}\ \dots\ x_{2,M}
\vdots
x_{N,1}\ x_{N,2}\ \dots\ x_{N,M}

出力

T 行。i 在线 写在方格 \mathrm{case}_i 的答案。 对于第


入力例 1

4
4 2 5
1 4
3 3
5 8
9 7
3 1 0
1
2
3
6 2 1
1 1
2 1
1 2
2 2
1 1
2 1
8 3 102
13 14 25
20 19 32
32 8 27
19 31 19
8 12 5
27 39 4
30 28 21
40 17 18

出力例 1

2
0
4
256

1 个测试用例,(S_1,S_2) = (\lbrace 1,2 \rbrace,\lbrace 3,4 \rbrace),(\lbrace 3,4 \rbrace,\lbrace 1,2 \rbrace) 的 2 满足条件。 对于第

2 个测试用例,满足条件 (S_1,S_2) 不存在。