CF1734E题解

· · 题解

题意

给出一个质数 n(n\leq 350) 和一个长度为 n 的序列 b_1,b_2,b_3 \dots,b_n，保证对于 \forall 1 \leq i \leq n, 有 0\leq b_i \lt n，试构造一个 n\times n 的矩阵 a，满足：

$\bullet$ 对于 $\forall x_1, x_2 ,y_1,y_2\leq n$，有 $a_{x_1,y_1} +a_{x_2,y_2} \not\equiv a_{x_1,y_2} +a_{x_2,y_1}\pmod n$。 $\bullet$ 对于 $\forall i \leq n$，有 $a_{i,i} =b_i$。 ## 思路 完整地讲一下我是如何想到怎样构造的。 我们看到每一个条件，尝试去做到满足它们。 看到条件一，显而易见，这个基本上没有限制任何构造，容易满足。 而看到第二个条件的式子，将其转化一下，变为 $$a_{x_1,y_1} -a_{x_1,y_2} \not\equiv a_{x_2,y_1} -a_{x_2,y_2}\pmod n$$ 这有什么用呢，事实上，我们将一个原来的矩形两个相对的顶点相加不等的条件变为了两个矩形两个同行的顶点相减不等。 我们知道如果使两个数加上同一个值，他们的差不变，那么如果给原来合法的矩阵某一行全部同时加上一个数，那么得到的矩阵也合法。 有什么用呢？可以帮助我们达成条件三，也就是说如果我们可以在不满足条件三的情况下构造了一个合法的矩阵，那么可以通过给某一行的数字同时加上一个数字来达成条件三。 现在的三个条件就转化成了满足一个条件二即可。 假设我们如果有一个初始矩阵，我们现在考虑如何令它一定合法，为方便考虑，我们的初始矩阵上的每一个数字都是 $0$，即 $$ \begin{matrix} 0 & 0 & 0 &\cdots & 0\\ 0 & 0 & 0 &\cdots & 0\\ 0 & 0 & 0 &\cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 &\cdots & 0\\ \end{matrix} $$ 通过我们刚刚转化的式子得，简单点想，满足条件二事实上只需要每一对不在同一行的数字差值不等即可，那我们尝试控制差值，这里给出一种方案，我们可以使第一行差值为 $0$， 使第二行差值为 $1$，使第三行差值为 $2$，以此类推，即使第 $i$ 行的差值为 $i-1$，正好 $n$ 行，我们正好用到差值为 $n-1$ 时停下，也就是说，我们的矩阵现在长这样： $$ \begin{matrix} 0 & 0 & 0 &\cdots & 0\\ 0 & 1 & 2 &\cdots & n-1\\ 0 & 2 & 4 &\cdots & 2\times(n-1)\mod n\\ \vdots &\vdots & \vdots &\ddots & \vdots\\ 0 & n-1 & 2\times(n-1)\mod n &\cdots & (n-1)\times(n-1)\mod n \\ \end{matrix} $$ 这时，就有人有疑问了，这样子构造会不会仍不合法，我们定义 $i,j$ 为两个差值，$k$ 为一个系数，那么是否可能有 $\exists i,j,k(i\neq j,0\leq i,j\leq n-1,1\leq k\leq n-1)$ 使得 $k\times (n-i)\equiv k\times(n-j) \pmod n$，比如说 $2\times (8-2)\equiv 2\times(8-6) \pmod n

No,no,no,不会存在这样的情况，为什么呢？我们发现

k\times (n-i)\equiv k\times(n-j) \pmod n\iff k\times(i-j)\equiv 0 \pmod n

也就是只有 i,j 的两个差值的差值与 k 的乘积为 n 的倍数时，才可能出现这样的情况，但是

\because i\neq j,0\leq i,j\leq n-1,1\leq k\leq n-1 \therefore 1\leq i-j\leq n-1,1\leq k\leq n-1 \because n \in \text{primes} \therefore \forall 1\leq x,y \leq n-1,x\times y\not\equiv 0\pmod n \therefore \forall 1\leq i-j,k \leq n-1,k\times (i-j)\not\equiv 0\pmod n

所以我们可以证明这样是一定正确的。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int num=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))num=(num<<1)+(num<<3)+(ch&15),ch=getchar();
    return num;
}
int a[400][400];
int main(){
    int n=read();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            a[i][j]=(a[i][j-1]+i-1)%n;
            //第i行的差值为i-1
        }
    }
    for(int i=1;i<=n;++i){
        int x=read()-a[i][i];
        //调整矩阵 
        for(int j=1;j<=n;++j){
            a[i][j]=(a[i][j]+x+n)%n;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",a[i][j]);
        }
        puts("");
    }
}

总结

这道题的瓶颈主要在于第二个条件的转换，以及条件的化简，对于矩阵的正确性的证明在做题时很容易会漏掉，但是它是值得注意的，做题时应留心。