【题意】给定大矩阵的边长H和W,给每格填数(<=|10^9|),要求大矩形总和为正数,而每个h*w的小矩形总和为负数,求构造方式。
【算法】数学
【题解】结论题。
★当h|H&&w|W(H是w的倍数,W是w的倍数)时,每个小矩阵之和加起来翻倍刚好成为大矩阵,无解。
当不为倍数时,显然会有多余的行列,我们尝试一种构造方式使多余的行列起作用。
1.从0计数,在h倍数行全部填正数1000(h-1)-1,在其他行全部填负数-1000(行是倍数时换成列,同理)。
这样构造,在h行范围内只有一行正数,每列之和都是-1。而论总和而言,多余行也有一行正数,小矩阵不满,所以每列至少多出1000-500,解决问题。
2.另一种构造方式,从1计数,在每个h*w倍数处填-1000*(h*w-1)-1,其它地方填1000,这样只要有一多余行列,多的若干个1000就可以将矩阵变成正数。
关键在第一个倍数无解的结论,有解时只要利用多余行列构造即可。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f; int N,M,n,m; int main()
{
scanf("%d%d%d%d",&N,&M,&n,&m);
if(N%n==&&M%m==){printf("No");return ;}
printf("Yes\n");
for(int i=;i<=N;i++){
for(int j=;j<=M;j++)
printf("%d ",i%n||j%m?:-*(n*m-)-);
printf("\n");
}
return ;
}