分析:有一个n*m的数组a,对应n*m的数组b,想让b=0的下标的a的数组之和等于b=1的下标的a的数组之和,你可以进行k*k的范围所有数字全部加任意数。
求出子矩阵里0和1的差值;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){
int n,m,k;cin>>n>>m>>k;
ll a[n+10][m+10],b[n+10][m+10],cz[n+10][m+10];
ll sum=0;//0部分和1部分的差值
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
char x;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>x;
if(x=='0')b[i][j]=-1;
else b[i][j]=1;
cz[i][j]=cz[i-1][j]+cz[i][j-1]-cz[i-1][j-1]+b[i][j];
if(b[i][j]==1)sum+=a[i][j];
else sum-=a[i][j];
}
}
int g=0;
for(int i=k;i<=n;i++){//算子矩阵的差值并找出所有子矩阵的gcd
for(int j=k;j<=m;j++){
int num=abs(cz[i][j]-cz[i-k][j]-cz[i][j-k]+cz[i-k][j-k]);
if(g==0)g=num;
else g=__gcd(g,num);
}
}
if(sum==0||(g!=0&&abs(sum)%g==0))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
int t;cin>>t;
while(t--){
sol();
}
}