题意

构造一个$n \times m$的矩阵$A$，且$1 \leq A_{i,j} \leq 25$，使得不存在点对$(x_1,x_2,y_1,y_2)$使得$A_{x_1,y_1},A_{x_1,y_2},A_{x_2,y_1},A_{x_2,y_2}$不全相等，换言之一个矩形边框四个角不全相等。

$1 \leq n,m \leq 500$

Solution

是个结论题~:

结论

$A_{i,j}=(\lfloor\frac{i}{23}\rfloor\lfloor\frac{j}{23}\rfloor+i+j)~ mod ~ 23+1$

考虑构造$P \times P$矩阵$B_k$，填入$[1,P]$，其中$P$是一个质数,$k$是一个给定整数。

那么我们可以这样构建：

$B_{i,j}=(i+j+k)~mod~p+1$

我们尝试用$P \times P$个这样的矩阵构造一个$P^2 \times P^2$的矩阵：

设$A_{i,j}$表示该位置的矩阵是$B_k$,有：

$k=(i \times j)~mod~P$

例如$P=3$的时候，矩阵如下：

$A=\begin{pmatrix} B_0&B_0&B_0\\ B_0&B_1&B_2\\ B_0&B_2&B_1\\ \end{pmatrix}$

现在证明正确性：

1. 对于$i_1=i_2$或$j_1=j_2$并且相邻，即同行或同列且相邻：

因为$B_k$中每一行每一列数字都不相同，在最多只填$P$个矩阵的前提下，可以保证不会出现$k$相同的矩阵

2. 四个矩阵，构成一个大正方形

考虑四个矩阵坐标为$(i,j),(i+1,j),(i,j+1),(i+1,j+1)$

则$k_1=ij~mod~p,k2=ij+j~mod~p,k3=ij+i~mod~p,k4=ij+i+j+1~mod~p$

令$ij=k$

若$k_1=k_2=k_3$，则可以得出$j=n_1k,i=n_2k$。

$k_4=(n_1+n_2)k+1~mod~p \not ={k}$

类似情况同理。