AT_KeioPC2025_d.Can I Press Them All?

在 $M$ 维空间中给定 $N$ 个点，第 $i$ 个点的坐标为 $(x_{i,1},x_{i,2},\dots,x_{i,M})$。同时给定一个非负整数 $D$。

请计算满足以下条件的 $(S_1, S_2)$ 这对 $\lbrace 1,2,\dots,N \rbrace$ 的子集的数量，并对 $998244353$ 取模：

• 对于每个 $1 \le i \le N$，$i$ 只属于 $S_1$ 或 $S_2$，但不能同时属于或都不属于。
• 对于任意 $c\in\{1,2\}$，如果 $a, b \in S_c$，那么 $\sum_{i=1}^M |x_{a,i} - x_{b,i}| \le D$ 必须成立。

给定 $T$ 组测试数据，分别输出每组的答案。

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

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

每组测试数据 $\mathrm{case}_i$ 格式如下：

$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$ 行输出第 $i$ 个测试用例的答案。

样例解释 1

对于第 $1$ 个测试用例，满足条件的 $(S_1, S_2)$ 有 $2$ 个，分别是 $(\lbrace 1,2\rbrace, \lbrace 3,4\rbrace)$ 和 $(\lbrace 3,4\rbrace, \lbrace 1,2\rbrace)$。

对于第 $2$ 个测试用例，不存在满足条件的 $(S_1,S_2)$。

数据范围

• $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$
• 输入均为整数。

由 ChatGPT 5 翻译