## 【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;
const int LIM = 101;
struct Matrix {
int v[LIM][LIM];
int size;
};

inline LL getSum(LL n) {
return n * (n * n + 1) / 2;
}

Matrix odd_msquare(int n) {
Matrix ret = {{0}, n};
int lim = n * n;
int r = 0, c = n / 2;
for (int i = 1; i <= lim; i++) {
ret.v[r][c] = i;
int nr = (r - 1 + n) % n;
int nc = (c + 1 + n) % n;
if (ret.v[nr][nc]) r++;
else r = nr, c = nc;
}
return ret;
}

inline void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}

Matrix m4_msquare(int n) {
Matrix ret = {{0}, n};
int crt = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ret.v[i][j] = crt;
crt++;
}
}
int lim = n / 2;
for (int i = 0; i < lim; i += 4) {
for (int j = 0; j < n; j += 4) {
if (i + 2 == lim && j > lim) break;
if (j + 2 == lim && i + 2 == lim) {
for (int k = 0; k < 2; k++) {
for (int m = 0; m < 4; m++) {
if (k == m || k == 4 - m - 1)
swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
}
}
} else {
for (int k = 0; k < 4; k++) {
for (int m = 0; m < 4; m++) {
if (k == m || k == 4 - m - 1)
swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
}
}
}
}
}
return ret;
}

Matrix m4p2_msquare(int n) {
int m = (n - 2) / 4;
Matrix tmp = odd_msquare(n / 2), ret = {{0}, n};
for (int i = 0; i < tmp.size; i++)
for (int j = 0; j < tmp.size; j++)
tmp.v[i][j] = tmp.v[i][j] * 4 - 4;
for (int i = 0; i <= m; i++) {
for (int j = 0; j < tmp.size; j++) {
ret.v[i << 1][j << 1] = 4 + tmp.v[i][j];
ret.v[i << 1][(j << 1) + 1] = 1 + tmp.v[i][j];
ret.v[(i << 1) + 1][j << 1] = 2 + tmp.v[i][j];
ret.v[(i << 1) + 1][(j << 1) + 1] = 3 + tmp.v[i][j];
}
}
ret.v[m << 1][tmp.size - 1] = 1 + tmp.v[m][tmp.size >> 1];
ret.v[m << 1][tmp.size] = 4 + tmp.v[m][tmp.size >> 1];
ret.v[(m << 1) + 1][tmp.size - 1] = 2 + tmp.v[m][tmp.size >> 1];
ret.v[(m << 1) + 1][tmp.size] = 3 + tmp.v[m][tmp.size >> 1];
for (int j = 0; j < tmp.size; j++) {
ret.v[(m + 1) << 1][j << 1] = 1 + tmp.v[m + 1][j];
ret.v[(m + 1) << 1][(j << 1) + 1] = 4 + tmp.v[m + 1][j];
ret.v[((m + 1) << 1) + 1][j << 1] = 2 + tmp.v[m + 1][j];
ret.v[((m + 1) << 1) + 1][(j << 1) + 1] = 3 + tmp.v[m + 1][j];
}
ret.v[(m + 1) << 1][tmp.size - 1] = 4 + tmp.v[m + 1][tmp.size >> 1];
ret.v[(m + 1) << 1][tmp.size] = 1 + tmp.v[m + 1][tmp.size >> 1];
ret.v[((m + 1) << 1) + 1][tmp.size - 1] = 2 + tmp.v[m + 1][tmp.size >> 1];
ret.v[((m + 1) << 1) + 1][tmp.size] = 3 + tmp.v[m + 1][tmp.size >> 1];
for (int i = m + 2; i < tmp.size; i++) {
for (int j = 0; j < tmp.size; j++) {
ret.v[i << 1][j << 1] = 1 + tmp.v[i][j];
ret.v[i << 1][(j << 1) + 1] = 4 + tmp.v[i][j];
ret.v[(i << 1) + 1][j << 1] = 3 + tmp.v[i][j];
ret.v[(i << 1) + 1][(j << 1) + 1] = 2 + tmp.v[i][j];
}
}
return ret;
}

int main(void) {
LL s;
int n;
Matrix ans;
while (~scanf("%d%lld", &n, &s)) {
if (n == 1) printf("%10lld\n", s);
else if (n == 2) printf("You can't be like Shahjahan!\n");
else {
LL diff = s - getSum(n);
if (diff % n) printf("You can't be like Shahjahan!\n");
else {
LL add = diff / n;
if (n % 2) {
ans = odd_msquare(n);
} else {
if (n % 4) ans = m4p2_msquare(n);
else ans = m4_msquare(n);
}
for (int i = 0; i < ans.size; i++) {
for (int j = 0; j < ans.size; j++) {
if (j) putchar(' ');
}
putchar('\n');
}
}
}
putchar('\n');
}
return 0;
}