配点 : 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) 不存在。