← 返回题目列表

Codeforces · 2178/I

I. 数字或烟花

中文机器翻译题面 查看原题

现在所有的礼物都已送达,北极终于平静了——是时候用一场壮观的新年烟花表演来庆祝了!

北极被建模为笛卡尔平面,$$$n$$$ 城市位于不同的格点上。您还将获得一个整数 $$$k$$$。

对于城市的真子集$$$^{\text{*}}$$$ $$$T$$$($$$T$$$ 可能为空),我们定义其 爆发力 如下:

  1. $$$T$$$的每个城市都会燃放烟花。
  2. 对于每个城市 $$$c$$$ 不 在$$$T$$$中,令$$$f$$$为从距离$$$c$$$恰好为$$$\sqrt{k}$$$欧几里德距离$$$^{\text{†}}$$$的城市发射的烟花数量。将号码 $$$(f+1)$$$ 分配给该城市 $$$c$$$。 $$$T$$$ 的
  3. 的 爆发力 是步骤 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$$$。

示例

输入
复制

4
3 1
1 2
2 1
2 2
2 20000
1 1
100 100
9 5
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
13 25
50 50
55 50
54 53
53 54
50 55
47 54
46 53
45 50
46 47
47 46
50 45
53 46
54 47

输出
复制

16
3
8255
560112

注意

在第一个测试用例中,下面是 $$$2^3-1=7$$$ 可能的烟花放置位置。分配给不在 $$$T$$$ 中的城市的数字被圈出。

总计 爆发力 是 $$$(1\cdot 1\cdot 1)+(1\cdot 2)+(2\cdot 1)+(2\cdot 2)+(3)+(2)+(2)=16$$$。

在第二个测试用例中,有 $$$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$$$。