题解：CF2081F Hot Matrix

· · 题解

神秘构造题。不妨设 n \ge 2。

显然，当 n 是奇数的时候，记 m=\frac{n-1}{2}，有 a_{m+1,*} = a_{*,m+1}=m，矛盾，不妨设 n=2m 是偶数。

考虑 a 中 m \times m 的子矩形 b_{1 \sim m,1 \sim m}。其中 a_{i,j} \in \{b_{i,j},n-b_{i,j}-1\}，两种情况分别称之为 c_{i,j} \in \{0,1\}。将其确定后整个矩阵也确定了。设 x 和 y 是 a 中横相邻两个数，则横相邻的两个数会出现 (x,y)、(y,x)、(n-x,n-y)、(n-y,n-x)。

那么这个 m \times m 的矩形需要满足：

  1. 横边界与竖边界上的数互不相同；
  2. 对于每个 (x,y)（x \neq y），在矩形中存在两个相邻的位置 (i_1,j_1)(i_1,j_1+1) 和 (i_2,j_2)(i_2,j_2+1) 使得 \{b_{i_1,j_1},b_{i_1,j_1+1}\} = \{b_{i_2,j_2},b_{i_2,j_2+1}\} = \{x,y\}；

首先看怎么生成 b，我们使用经典的 zig-zag 方法。具体而言，生成序列 d=[1,2,m,3,m-1,\cdots]。令 b_{i,j} = d_i+d_j-1 即可。

然后是怎么生成 c（同时确定 b 和 c 后，整个矩形也确定了）。一个简单的想法是，我们让 c 的自由度不会太高——取 X 和 Y 为 01 序列，则 c_{i,j} = X_i \oplus Y_j。

这样，c_{i,j} \oplus c_{i,j+1} = Y_j \oplus Y_{j+1} 与 i 无关，更好控制。

按照上述生成 d 的方式，一定有 j_1+j_2=m。当 m 是奇数的时候，一定有 j_1 \neq j_2，所以我们让 Y_{j} \oplus Y_{j+1} 和 Y_{m-j} \oplus Y_{m-j+1} 不同就行——这是很容易实现的。X 同理。

当 m 是偶数的时候，核心问题出在 j_1=j_2 = \frac{m}{2} 时——这样 c_{i_1,j_1} \oplus c_{i_1,j_1+1} = c_{i_2,j_2} \oplus c_{i_2,j_2+1} 一定成立。咋办？

以 m=6 为例，观察一下我们构造出来的 b：

126354
231465
615243
342516
564132
453621

它是中心对称的。接下来，我们将给出神之一笔：将 c 中两个区域中的数异或 1。

容易验证，这样得到的 c' 一定符合要求。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3000+10;
int T,n,m,k,a[MAXN][MAXN],c[MAXN][MAXN],vis[MAXN];
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) {
        cin>>n;
        if(n==1) {cout<<"YES\n0\n";continue ;}
        if(n%2) {cout<<"NO\n";continue;}
        cout<<"YES\n",m=n/2;
        ffor(i,1,m) vis[i]=0;
        int l=2,r=m;a[1][1]=1;
        ffor(i,2,m) if(i%2==0) a[1][i]=l++; else a[1][i]=r--;
        ffor(i,2,m) a[i][1]=a[1][i];
        ffor(i,2,m) ffor(j,2,m) a[i][j]=((a[i][1]-2+a[1][j])%m+m)%m+1;
        ffor(i,2,m) {
            int dt=min(i-1,m-i+1);
            if(vis[dt]) c[1][i]=c[1][i-1]^1;
            else c[1][i]=c[1][i-1],vis[dt]=1;   
        }
        ffor(i,2,m) c[i][1]=c[1][i];
        ffor(i,2,m) ffor(j,2,m) c[i][j]=c[i][1]^c[1][j];
        if(m%2==0) {
            int k=m/2;
            ffor(i,1,k-1) ffor(j,k+2,m) c[i][j]^=1;
            ffor(i,k+1,m) ffor(j,1,k) c[i][j]^=1;
            ffor(i,k+2,m) ffor(j,1,k-1) c[i][j]^=1; 
        }
        ffor(i,1,m) ffor(j,1,m) {
            --a[i][j];
            if(c[i][j]) a[i][j]=n-1-a[i][j];
            a[i][n-j+1]=a[n-i+1][j]=n-1-a[i][j];
            a[n-i+1][n-j+1]=a[i][j];
        }
        ffor(i,1,n) {
            ffor(j,1,n) cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
    return 0;
}