CF1734E Rectangular Congruence 题解

jiangtaizhe001 · 2023-02-19 20:55:07 · 题解

可能更好的阅读体验

题目传送门 to luogu

为什么只有 VP 才会遇到这种简单 E。

题目大意

给定一个质数 n 和长度为 n 的序列 b，要求构造一个 n\times n 矩阵 a，满足所有 r_1,r_2,c_1,c_2（1\le r_1<r_2\le n，1\le c_1<c_2\le n），有 a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1}\pmod n，同时 a_{i,i}=b_i。
数据范围：2\le n\le 350。

题目解析

对原式移项，得到 a_{r_1,c_1}-a_{r_1,c_2}\not\equiv a_{r_2,c_2}-a_{r_2,c_2}\pmod n。
也就是说，对于任意的 1\le l<r\le n，(a_{l,i}-a_{r,i})\bmod n 两两不同，换句话说，构成一个 0\sim n-1 的一个排列。
注意到我们如果给一行都加上一个数不会影响 a_{l,i}-a_{r,i}，所以 a_{i,i}=b_i 的限制可以忽略，只需要最后整行加上一个数即可。

接下来考虑如何得到一个任意的合法的 a。
首先假设 a_{2,i}-a_{1,i}=i，然后考虑怎么构造 a_{3,i}。
我们发现直接让 a_{3,i}-a_{2,i}=i 即可。
换句话说可以直接，a_{i,j}=i\times j\bmod n。
我们来证明这样是正确的。

换句话说，对于任意的 0\le x<n，xy\bmod n（0\le y<n）两两不同。
使用反证法，假设 0\le i<j<n 有 xi\equiv xj\pmod n。
发现因为 n 是质数，\gcd(x,n)=1，所以 i\equiv j\pmod n，得到 i=j，矛盾，所以假设不成立，证毕。（类似于欧拉定理证明里的一步）

最后为了让 a_{i,i}=b_i，所以得到 a_{i,j} 的通项：

int n,b[maxn];
int main(){
    n=read(); int i,j; for(i=1;i<=n;i++) b[i]=read();
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) print((i*j-i*i%n+b[i]+n)%n),pc(" \n"[j==n]);
    return 0;
}