Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)

题目大意：

给定两个 \(n\times m\) 矩阵 \(A\) ， \(B\) 和一个常数 \(x\)

现在对于 \(A\) 操作，每次可以选择一行或者一列连续的 \(x\) 个，一起改变同一个数值 \(v\in \Z\)

判断是否可以由 \(A\) 变成 \(B\)

显然可以先将 \(A,B\) 作差，转化为操作成0矩阵

进一步，我们将 \(A\) 矩阵行内差分，使得每次行操作变为一个单点 \(A_{i,j}+v\) ，一个单点 \(A_{i,j+x}-v\)

在此基础上，继续差分即可将行列操作都转化为单点操作

此时容易发现， \(A_{i,j}\) 的数值有关联的部分都是 \(A_{i,j},A_{i+x,j},A_{i,j+x}\cdots A_{i+ax,j+bx}\)

也就是相差 \(x\) 的，考虑可以将这一部分子矩形提取出来，这样问题变成了

每次操作一个数 \(A_{i,j}+v\) ，可以选择相邻一个数 \(A_{i,j+1}\) 或 \(A_{i+1,j}\) 去 \(-v\)

对于每个这样的子问题，容易发现有解的充要条件：子矩阵元素和为0

（可以依次考虑每个元素贪心构造方案）

如此可以 \(O(nm)\) 判定

const int N=1010,INF=1e9+10;

int n,m,k;
ll A[N][N],B[N][N];
int V[N][N];

int main(){
	rep(kase,1,rd()) {
		n=rd(),m=rd(),k=rd();
		rep(i,1,n+1) rep(j,1,m+1) A[i][j]=V[i][j]=0;
		rep(i,1,n) rep(j,1,m) A[i][j]=rd();
		rep(i,1,n) rep(j,1,m) A[i][j]-=rd();
		rep(i,1,n+1) drep(j,m+1,1) A[i][j]-=A[i][j-1];
		drep(i,n+1,1) rep(j,1,m+1) A[i][j]-=A[i-1][j];
        // 3 次作差
		int f=1;
		rep(i,1,n+1) rep(j,1,m+1) if(!V[i][j]) {
			ll s=0;
            // 子问题判定
			for(int a=i;a<=n+1;a+=k) for(int b=j;b<=m+1;b+=k) {
				V[a][b]=1;
				s+=A[a][b];
			}
			f&=s==0;
		}
		puts(f?"Yes":"No");
	}
}