D - Can I Press Them All? Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 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) は存在しません。