#include using namespace std; typedef vector VI; typedef vector VVI; typedef set SI; int A92[] = {1, 1, -1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, -1, -1, -1, 1}; int B92[] = {1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, -1}; int C92[] = {1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1}; int D92[] = {1, 1, 1, -1, 1, 1, 1, -1, 1, -1, -1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1}; SI paley1, paley2; struct MAT { VVI a; int n; MAT(int _n) { n = _n; a.resize(n); for (int i = 0; i < n; i++) { a[i].resize(n, 0); } } }; MAT construct_circulant_symmetric_matrix(int first_row[], int n) { MAT R(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { R.a[i][j] = first_row[(n+j-i) % n]; } } return R; } MAT get_negative(MAT A) { int n = A.n; MAT B(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { B.a[i][j] = -A.a[i][j]; } } return B; } MAT join_mat(MAT A, MAT B, MAT C, MAT D, int n) { /* Given 4 matrices A, B, C, D, each of order 'n', we return a new matrix of order '2*n' in the following way: | A B | | C D | */ MAT R(2*n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { R.a[i][j] = A.a[i][j]; R.a[i][n+j] = B.a[i][j]; R.a[n+i][j] = C.a[i][j]; R.a[n+i][n+j] = D.a[i][j]; } } return R; } MAT construct_williamson_92() { /* 4*k = 92, k = 23 Given A, B, C, D which are symmetric and circulant matrices of order 'k', by Williamson construction, we can construct a Hadamard matrix of order '4*k' by constructing the following matrix: | A B C D | |-B A D -C | |-C -D A B | |-D C -B A | */ MAT A = construct_circulant_symmetric_matrix(A92, 23); MAT B = construct_circulant_symmetric_matrix(B92, 23); MAT C = construct_circulant_symmetric_matrix(C92, 23); MAT D = construct_circulant_symmetric_matrix(D92, 23); MAT nB = get_negative(B); MAT nC = get_negative(C); MAT X = join_mat(A, B, nB, A, 23); MAT Y = join_mat(C, D, D, nC, 23); MAT nY = get_negative(Y); MAT R = join_mat(X, Y, nY, X, 46); // Resultant matrix has order 92. return R; } #ifdef DEBUG bool is_good(MAT A) { int N = A.n; for (int i = 0; i < N*N; i++) { if (A.a[i / N][i % N] != -1 && A.a[i / N][i % N] != 1) return false; // If all elements are -1 or 1, then if (i/N) == (i%N), the sum will // automatically be equal to N^2. No need to check for that. if ((i / N) == (i % N)) continue; int sum = 0; for (int k = 0; k < N*N; k++) { int inx1 = (i % N) * N + (k % N); int inx2 = (i / N) * N + (k % N); sum += A.a[inx1 / N][inx1 % N] * A.a[inx2 / N][inx2 % N]; } if (sum != 0) return false; } return true; } #endif bool has_solution(int n) { return n == 1 || n == 2 || (n % 4 == 0); } VI get_prime_residues(int n) { VI is_square(n, -1); is_square[0] = 0; for (int i = 1; i < n; i++) { int res = (i * i) % n; if (res < 0) res += n; is_square[res] = 1; } return is_square; } VI get_square_residues(int n) { int a1, a0, p;// X^2 = a1*X + a0 if (n == 25) a1 = -4, a0 = -2, p = 5; else a1 = -6, a0 = -3, p = 7; // n = 49 VI is_square(n, -1); is_square[0] = 0; for (int i = 0; i < p; i++) { for (int j = 0; j < p; j++) { if (i + j == 0) continue; int res1 = (a1 * i * i + 2 * i * j) % p; int res2 = (a0 * i * i + j * j) % p; if (res1 < 0) res1 += p; if (res2 < 0) res2 += p; is_square[p*res1 + res2] = 1; } } return is_square; } MAT expand_paley(MAT A, int n) { /* Every 0 in A is replaced by | 1 -1 | |-1 -1 | Every 1 in A is replaced by | 1 1 | | 1 -1 | Every -1 in A is replaced by |-1 -1 | |-1 1 | */ MAT R(2*n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (A.a[i][j] == 0) { R.a[2*i][2*j] = 1; R.a[2*i][2*j+1] = -1; R.a[2*i+1][2*j] = -1; R.a[2*i+1][2*j+1] = -1; } else if (A.a[i][j] == 1) { R.a[2*i][2*j] = 1; R.a[2*i][2*j+1] = 1; R.a[2*i+1][2*j] = 1; R.a[2*i+1][2*j+1] = -1; } else { R.a[2*i][2*j] = -1; R.a[2*i][2*j+1] = -1; R.a[2*i+1][2*j] = -1; R.a[2*i+1][2*j+1] = 1; } } } return R; } MAT get_solution(int n) { if (n == 1) { MAT ret(1); ret.a[0][0] = 1; return ret; } else if (n == 2) { MAT ret(2); ret.a[0][0] = ret.a[0][1] = ret.a[1][0] = 1; ret.a[1][1] = -1; return ret; } else if (n == 92) { // Use Williamson's construction, since Paley's construction won't work // for this case. return construct_williamson_92(); } else if (paley1.find(n) != paley1.end()) { // q is congruent to 3 mod 4. Constructing matrix of order (q+1). int q = n-1; VI is_square = get_prime_residues(q); MAT R(n); R.a[0][0] = 1; for (int i = 1; i < q+1; i++) { R.a[0][i] = 1; R.a[i][0] = -1; } for (int i = 0; i < q; i++) { for (int j = 0; j < q; j++) { if (i == j) R.a[i+1][j+1] = 1; else R.a[i+1][j+1] = is_square[(q+i-j) % q]; } } return R; } else if (paley2.find(n) != paley2.end()) { // q is congruent to 1 mod 4. Constructing matrix of order 2*(q+1). int q = (n/2)-1; MAT R2(q+1); for (int i = 1; i < q+1; i++) { R2.a[0][i] = 1; R2.a[i][0] = 1; } if (n == 52 || n == 100) { VI is_square = get_square_residues(q); int q_root; if (n == 52) q_root = 5; else q_root = 7; for (int i = 0; i < q; i++) { for (int j = 0; j < q; j++) { int i1 = i / q_root, j1 = j / q_root; int block = (i1 - j1 + q_root) % q_root; int ni = i - i1*q_root, nj = j - j1*q_root; int inx = q_root * block + (ni - nj + q_root) % q_root; R2.a[i+1][j+1] = is_square[inx]; if (i%q_root >= j%q_root && i >= j) cout << 0 << ""; if (i%q_root < j%q_root && i >= j) cout << 1 << ""; if (i%q_root >= j%q_root && i < j) cout << 1 << ""; if (i%q_root < j%q_root && i < j) cout << 2 << ""; } cout << endl; } cout << endl; } else { VI is_square = get_prime_residues(q); for (int i = 0; i < q; i++) { for (int j = 0; j < q; j++) { R2.a[i+1][j+1] = is_square[(q+i-j) % q]; } } } MAT R = expand_paley(R2, q+1); return R; } // else Kronecker's multiplication can be used to generate matrices of // larger orders from matrices of smaller orders. MAT A = get_solution(n / 2); MAT nA = get_negative(A); MAT R = join_mat(A, A, A, nA, n/2); return R; } void construct_paley_sets() { /* No.s which can be constructed by Paley's construction 1 (q = 3 mod 4): Matrix of order (q+1) can be constructed. 4 = (3 + 1), 8 = (7 + 1), 12 = (11 + 1), 20 = (19 + 1), 24 = (23 + 1), 32 = (31 + 1), 44 = (43 + 1), 48 = (47 + 1), 60 = (59 + 1), 68 = (67 + 1), 72 = (71 + 1), 80 = (79 + 1), 84 = (83 + 1) No.s which can be constructed by Paley's construction 2 (q = 1 mod 4): Matrix of order 2*(q+1) can be constructed. 28 = (13 + 1) * 2, 36 = (17 + 1) * 2, 52 = (5^2 + 1) * 2, 76 = (37 + 1) * 2, 100 = (7^2 + 1) * 2 Others can simply be constructed from smaller matrices, since the Kronecker product of 2 Hadamard matrices of order n & m, is also a Hadamard matrix of order n*m. 16 = 2 * 8, 40 = 2 * 20, 56 = 2 * 28, 64 = 2 * 32, 88 = 2 * 44, 96 = 2 * 48 */ paley1.insert(4), paley1.insert(8), paley1.insert(12), paley1.insert(20), paley1.insert(24); paley1.insert(32), paley1.insert(44), paley1.insert(48), paley1.insert(60); paley1.insert(68), paley1.insert(72), paley1.insert(80), paley1.insert(84); paley2.insert(28), paley2.insert(36), paley2.insert(52); paley2.insert(76), paley2.insert(100); } int main() { // freopen("input10.txt", "r", stdin); freopen("output10.txt", "w", stdout); construct_paley_sets(); int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); if (!has_solution(n)) { printf("NO\n"); } else { printf("YES\n"); MAT ans = get_solution(n); int len = ans.n; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (i + j == 0) printf("%d", ans.a[i][j]); else printf(" %d", ans.a[i][j]); } } printf("\n"); #ifdef DEBUG printf("VALID: %d\n", is_good(ans)); #endif } } }