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 翻译