pro:给定N*M的矩阵,每次操作一个位置,它会增加2,周围4个位置会增加1。给定初始状态,求一种方案,使得最后的数都为0;(%3意义下。

sol:(N*M)^3的复杂度的居然过了。          好像标程是M^3的,因为第一排确定了,后面的都确定了。所以我们只要设关于第一排的方程,那么跑下来,第N+1排的都为0,则合法。

(此题由于3的特殊性,x关于3的逆元=x;所以不用求逆元

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn][maxn],ans[maxn];
int x[]={,,,-};
int y[]={,-,,};
void Guass(int N)
{
rep(i,,N-){
int t=i;
rep(j,i+,N-) if(a[j][i]>a[t][i]) t=j;
if(i!=t) rep(j,i,N) swap(a[i][j],a[t][j]);
if(!a[i][i]) continue;
rep(j,i+,N-){
if(!a[j][i]) continue;
int t1=a[i][i],t2=a[j][i];//保留,不能直接带进去
rep(k,i,N)
a[j][k]=((a[j][k]*t1-a[i][k]*t2)%+)%;
}
}
for(int i=N-;i>=;i--){
a[i][N]=a[i][N]*a[i][i]%;
rep(j,,i-)
a[j][N]=((a[j][N]-a[i][N]*a[j][i])%+)%;
}
}
int main()
{
int T,N,M,S,t,p;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M); S=N*M;
rep(i,,S) rep(j,,S) a[i][j]=;
rep(i,,N-) rep(j,,M-){
t=i*M+j;
scanf("%d",&a[t][S]);
a[t][S]=-a[t][S];
}
rep(i,,S-) a[i][i]=;
rep(i,,N-)
rep(j,,M-){
t=i*M+j;
rep(k,,) {
if(i+x[k]>=&&i+x[k]<N&&j+y[k]>=&&j+y[k]<M){
a[(i+x[k])*M+j+y[k]][t]=;
}
}
}
Guass(S);
int res=;
rep(i,,S-) res+=a[i][S];
printf("%d\n",res);
rep(i,,S-){
p=i/M+; t=i%M+;
if(a[i][S]) printf("%d %d\n",p,t);
if(a[i][S]==) printf("%d %d\n",p,t);
}
}
return ;
}
05-04 02:03