[ARC140E] Not Equal Rectangle

Genius_Star · 2026-04-03 15:52:43 · 题解

比较牛的题，场切了。

思路：

容易发现，我只要构造出一个很大的满足条件的矩阵，随便取中间一个 n \times m 的子矩阵都满足。

看到构造先打表，先打方阵的表，场上瞪了半小时，发现 n \times n 的方阵构造 M_{i, j} = (i + j) \bmod n 是正确的，因为显然每行每列不存在元素相等。

于是想到用这个 n \times n 的去拼一个大矩阵；单独这一个矩阵不太好，考虑它的循环位移，即 M_{k, i, j} = (i + j + k) \bmod n。

考虑用 n \times n 个上面矩阵的循环位移（称作一个块）去拼一个 n^2 \times n^2 的大矩阵，刚开始没想到什么思路去放，先假设存在 x_1, y_1, x_2, y_2 使得 a_{x_1, y_1} = a_{x_1, y_2} = a_{x_2, y_1} = a_{x_2, y_2} 会怎么样？显然这四个数分别在四个块中，设分别在 M_a, M_b, M_c, M_d，那么可以得到：

整理一下可以得到：

想要使得不存在 a, b, c, d 满足上面这个条件，想到构造对于一个在 i 行 j 列的块，其是 M_{ij}。

那么设 a, b, c, d 对应的行列分别是 x_1', y_1', x_2', y_2'，于是条件等价于：

因为显然 x_1', y_1', x_2', y_2' < n，那么只要 n 是质数，那么一定满足上面的条件。

于是取 n = 23，可以构造出 23^2 \times 23^2 的大矩阵，且其包含 500 \times 500 的子矩阵，于是构造 ans_{i, j} = (i + j + \lfloor \frac{i}{23} \rfloor \lfloor \frac{j}{23} \rfloor) \bmod 23 + 1 即可。

完整代码：

 #include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define ctz(x) __builtin_ctz(x)
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 505, M = 1e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
mt19937 R(time(0));
int n, m, mod = 23;
int A[M];
inline int id(int i, int j){
    return i * m + j;
}
inline bool check(){
    for(int x1 = 0; x1 < n; ++x1){
        for(int x2 = x1 + 1; x2 < n; ++x2){
            for(int y1 = 0; y1 < m; ++y1){
                for(int y2 = y1 + 1; y2 < m; ++y2){
                    if(A[id(x1, y1)] == A[id(x1, y2)] && A[id(x1, y2)] == A[id(x2, y1)] && A[id(x2, y1)] == A[id(x2, y2)])
                      return 0;
                }
            }
        }
    }
    return 1;
}
int main(){
    n = read(), m = read();
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            A[id(i, j)] = (i + j + (i / mod) * (j / mod)) % mod + 1;
            write(A[id(i, j)]);
            putchar(' ');
        }
        putchar('\n');
    }
    // if(check())
    //   puts("Yes");
    // else    
    //   puts("No");
    return 0;
}