time limit per test
2 seconds
memory limit per test
256 megabytes
A progressive square of size nn is an n×nn×n matrix. Maxim chooses three integers a1,1a1,1, cc, and dd and constructs a progressive square according to the following rules:
ai+1,j=ai,j+cai+1,j=ai,j+c
ai,j+1=ai,j+dai,j+1=ai,j+d
For example, if n=3n=3, a1,1=1a1,1=1, c=2c=2, and d=3d=3, then the progressive square looks as follows:
⎛⎝⎜1354687911⎞⎠⎟(1473695811)
Last month Maxim constructed a progressive square and remembered the values of nn, cc, and dd. Recently, he found an array bb of n2n2 integers in random order and wants to make sure that these elements are the elements of that specific square.
It can be shown that for any values of nn, a1,1a1,1, cc, and dd, there exists exactly one progressive square that satisfies all the rules.
Input
The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The first line of each test case contains three integers nn, cc, and dd (2≤n≤5002≤n≤500, 1≤c,d≤1061≤c,d≤106) — the size of the square and the values of cc and dd as described in the statement.
The second line of each test case contains n⋅nn⋅n integers b1,b2,…,bn⋅nb1,b2,…,bn⋅n (1≤bi≤1091≤bi≤109) — the elements found by Maxim.
It is guaranteed that the sum of n2n2 over all test cases does not exceed 25⋅10425⋅104.
Output
For each test case, output "YES" in a separate line if a progressive square for the given nn, cc, and dd can be constructed from the array elements aa, otherwise output "NO".
You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.
Example
Input
Copy
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
Output
Copy
NO YES YES NO NO
解题说明：此题是一道数学题，从题目意思中的得知，这种方阵仅由n,c,d以及a[0][0]决定，所以它唯一可能对应的方阵我们可以找到，然后就是比较两个方阵里的数能不能对应即可。这里可以采用集合来做，排序后逐一比较。
#include <bits/stdc++.h>
using namespace std;int solve(int n, int c, int d, vector<int> a)
{sort(a.begin(), a.end());vector<int> q;for (long long i = 0; i < n; i++){for (long long j = 0; j < n; j++) {q.push_back(a[0] + c * i + d * j);}}sort(q.begin(), q.end());for (long long i = 0; i < n * n; i++){if (a[i] != q[i]){return false;}}return true;
}int main()
{int t;cin >> t;while (t--) {int n, c, d;cin >> n >> c >> d;vector<int> a(n * n);for (long long i = 0; i < n * n; i++){cin >> a[i];}if (solve(n, c, d, a)){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
}
