← 返回题目列表

Codeforces · 1955/B

B. 渐进方形

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

大小为 $$$n$$$ 的渐进正方形是 $$$n \times n$$$ 矩阵。 Maxim 选择三个整数 $$$a_{1,1}$$$、$$$c$$$ 和 $$$d$$$,并根据以下规则构建渐进平方:

$$$$$$a_{i+1,j} = a_{i,j} + c$$$$$$

$$$$$$a_{i,j+1} = a_{i,j} + d$$$$$$

例如,如果 $$$n = 3$$$、$$$a_{1,1} = 1$$$、$$$c=2$$$ 和 $$$d=3$$$,则渐进正方形如下所示:

$$$$$$ \begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix} $$$$$$

上个月 Maxim 构建了一个渐进正方形并记住了 $$$n$$$、$$$c$$$ 和 $$$d$$$ 的值。最近,他发现了一个由随机顺序的 $$$n^2$$$ 整数组成的数组 $$$b$$$,并希望确保这些元素是该特定正方形的元素。

可以证明,对于 $$$n$$$、$$$a_{1,1}$$$、$$$c$$$ 和 $$$d$$$ 的任何值,都恰好存在一个满足所有规则的渐进正方形。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le {10} ^ 4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$c$$$ 和 $$$d$$$ ($$$2 \le n \le 500$$$, $$$1 \le c, d \le 10^6$$$) - 正方形的大小以及 $$$c$$$ 和 $$$d$$$ 的值,如语句中所述。

每个测试用例的第二行包含 $$$n \cdot n$$$ 整数 $$$b_1, b_2, \dots, b_{n \cdot n}$$$ ($$$1 \le b_i \le 10^9$$$) — Maxim 找到的元素。

保证所有测试用例的 $$$n ^ 2$$$ 总和不超过 $$$25 \cdot {10} ^ 4$$$。

输出

对于每个测试用例,如果可以从数组元素 $$$a$$$ 构造给定 $$$n$$$、$$$c$$$ 和 $$$d$$$ 的渐进方块,则在单独的行中输出“YES”,否则输出“NO”。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

示例

输入 #1

5
3 2 3
3 9 6 5 7 1 10 4 8
3 2 3
3 9 6 5 7 1 11 4 8
2 100 100
400 300 400 500
3 2 3
3 9 6 6 5 1 11 4 8
4 4 4
15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15

输出 #1

NO
YES
YES
NO
NO