现在所有的礼物都已送达,北极终于平静了——是时候用一场壮观的新年烟花表演来庆祝了!
北极被建模为笛卡尔平面,$$$n$$$ 城市位于不同的格点上。您还将获得一个整数 $$$k$$$。
对于城市的真子集$$$^{\text{*}}$$$ $$$T$$$($$$T$$$ 可能为空),我们定义其 爆发力 如下:
- $$$T$$$的每个城市都会燃放烟花。
- 对于每个城市 $$$c$$$ 不 在$$$T$$$中,令$$$f$$$为从距离$$$c$$$恰好为$$$\sqrt{k}$$$欧几里德距离$$$^{\text{†}}$$$的城市发射的烟花数量。将号码 $$$(f+1)$$$ 分配给该城市 $$$c$$$。 $$$T$$$ 的
- 的 爆发力 是步骤 2 中分配的所有数字的乘积。
计算总和 爆发力 $$$T$$$ 超过所有 $$$2^n-1$$$ 城市的真子集 $$$T$$$。由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
$$$^{\text{*}}$$$真子集是不等于整个集合的任何子集。
$$$^{\text{†}}$$$两点 $$$(x, y)$$$ 和 $$$(p, q)$$$ 之间的欧氏距离定义为 $$$\sqrt{(x - p)^2 + (y - q)^2}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2\le n\le 31$$$, $$$1\leq k \leq2\cdot 10^4$$$)。
接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1\leq x_i, y_i\leq 100$$$) — 分别是第 $$$i$$$ 城市的 $$$x$$$ 和 $$$y$$$ 坐标。保证城市的坐标是两两不同的。
保证所有测试用例的$$$n^3$$$总和不超过$$$31^3$$$。
输出
对于每个测试用例,打印一个整数 - 模 $$$998\,244\,353$$$ 的总和 爆发力 城市的所有真子集 $$$T$$$。
示例
输入复制
43 11 22 12 22 200001 1100 1009 51 11 21 32 12 22 33 13 23 313 2550 5055 5054 5353 5450 5547 5446 5345 5046 4747 4650 4553 4654 47
输出复制
1638255560112
注意
在第一个测试用例中,下面是 $$$2^3-1=7$$$ 可能的烟花放置位置。分配给不在 $$$T$$$ 中的城市的数字被圈出。
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() |
在第二个测试用例中,有 $$$2^2-1=3$$$ 可能的烟花放置位置。对于每个展示位置,由于 $$$(1,1)$$$ 和 $$$(100,100)$$$ 的欧几里得距离为 $$$\sqrt{(100-1)^2+(100-1)^2}=\sqrt{19\,602}\neq\sqrt{20\,000}$$$,因此没有一个城市的烟花完全符合$$$\sqrt{k}$$$ 远。因此,编号 $$$1$$$ 被分配给每个没有烟花的城市。因此, 爆发力 对于每个 $$$T$$$ 来说是 $$$1$$$,答案是 $$$1+1+1=3$$$。






