【AtCoder2387】+/- Rectangle

The question

Construct a $H\times W$ Matrix , Meet the following conditions

• All elements are integers , And belongs to $[-10^9,10^9]$
• The sum of all elements is positive
• For each $h\times w$ The submatrix of , Its element sum is negative

Answer key

According to the example , The simplest idea is , Give satisfaction $xmodh=0$ And $ymodw=0$ The location of $(x,y)$ Marked as $-hw$, All the rest are marked as $1$
But there are counter examples
about $1\times 4$ Matrix ,$1\times 3$ The submatrix of , Will be marked as
$$\begin{array}{cccc}1& 1& -3& 1\end{array}$$ illegal , Can be marked as
$$\begin{array}{cccc}2& 2& -5& 2\end{array}$$

Consider improving this method , Mark the normal position as $k$,$xmodh=0$ And $ymodw=0$ The location of $(x,y)$ Marked as $-k(hw-1)-1$, The sum of the submatrix is -1, If you can find k, Then there is a solution .

It can be proved that $Hmodh=0$ And $Wmodw=0$ when , unsolvable , At this time, you can $H\times W$ The matrix of is exactly divided into integer numbers $h\times w$ Submatrix , And each submatrix is negative , Then the entire primitive matrix cannot sum to a positive number .

If the above conditions are not met , Then the original matrix is cut into several submatrixes , There are still some leftovers , The value of each cell of leftover materials is $k$, Just make $k$ Large enough , It must be able to offset a lot of the previous submatrix -1, therefore k The bigger the better .

When it is implemented, directly put k Card to the maximum .

Code

#include<cstdio> const int MAXN=505; int H,W,h,w; int arr[MAXN][MAXN]; int main() {
      scanf("%d%d%d%d",&H,&W,&h,&w); if(h==1&&w==1) {
      puts("No"); return 0; } long long sum=0; int k=999999999/(h*w-1); {
      sum=0; for(int i=1;i<=H;i++) for(int j=1;j<=W;j++) {
      if(i%h==0&&j%w==0) arr[i][j]=-k*(h*w-1)-1; else arr[i][j]=k; sum+=arr[i][j]; } if(sum>0) {
      puts("Yes"); for(int i=1;i<=H;i++) {
      for(int j=1;j<=W;j++) printf("%d ",arr[i][j]); puts(""); } return 0; } } puts("No"); return 0; }