做题时间:2022.9.23
\(【题目描述】\)
给定一个质数 \(n(2\leq n<350)\) 以及 \(n\) 个整数 \(b_1,b_2,...,b_n(0\leq b_i<n)\),构造一个 \(n\times n\) 的矩阵,要求满足:
- \(0\leq a_{i,j}<n\)
- \(a_{r_1,c_1}+a_{r_2,c_2} ≢ a_{r_1,c_2}+a_{r_2,c_1} \pmod n\)
- \(a_{i,i}=b_i\)
\(【输入格式】\)
第一行一个整数表示 \(n\)\
第二行 \(n\) 个整数表示 \(b_1,b_2,...,b_n\)
\(【输出格式】\)
共 \(n\) 行,表示答案矩阵 \(a\)
\(【考点】\)
构造,数论
\(【做法】\)
题目中有多个约束条件,可以先忽略其中一部分,然后再考虑
首先第2个约束条件相当于对于答案矩阵中每一个子矩阵左上顶点的值+右上顶点的值与左下顶点的值加右下顶点的值不同余,这个约束条件与点的行与列密切相关,可以考虑将 \(a\) 的值用行和列表示。稍加尝试可以发现 \(a_{i,j}=i\times j \mod n\) 同时满足条件1,2的要求。对于第3个条件,可以将所有的 \(a_{i,i}\) 变成 \(b_i\) ,并把同一行所有的 \(a\) 全部加上其差值,这样相当于在同余式两边同时加上两个 \(b_i-a_{i,i}\) ,结果不变。另外注意负数。
\(【代码】\)
#include<cstdio>
#include<iomanip>
using namespace std;
const int N=355;
int b[N],a[N][N],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) a[i][j]=i*j%n;
}
for(int i=1;i<=n;i++){
int add=b[i]-a[i][i];
for(int j=1;j<=n;j++){
a[i][j]+=add;
a[i][j]=(a[i][j]+n)%n;
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
标签:约束条件,int,矩阵,Congruence,CF1734E,Rectangular,顶点,include
From: https://www.cnblogs.com/Unlimited-Chan/p/16728701.html