昨晚开始写这题。。脑子像浆糊一样。中午直接重码然后就过了= =
高斯消元解异或方程组。。
暴力点的做法就是把每个点都当成一个未知数然后解方程。。O((nm)^3)似乎可过。。
然后显然我们确定了第一行后，整个矩阵就可以确定下来了。
至于快速判断是否合法。。直接递推到第m+1行，如果那一行上都是0就合法。（暴力应该也要用到这个）（原矩阵m行n列）
每种方案都去重新递推一次的显然是傻逼QAQ。。。
一开始先递推出，第m+1行上的每个点，与第一行中每个点的关系。。然后我们就得到了n个方程。
最后高斯消元解一下方程就行了QAQ。把自由元当成1处理，这样就不会出现全0了（数据保证有解）
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int maxn=42; 6 bool f[2][maxn][maxn],now,pre; 7 bool mp[maxn][maxn],ans[maxn][maxn]; 8 int i,j,k,n,m; 9 10 inline void gauss(){ 11 int i,j,k; 12 // for(i=1;i<=m;puts(""),i++)for(j=1;j<=m;j++)printf(" %d",mp[i][j]); 13 for(i=1;i<=m;i++){ 14 for(j=i;!mp[j][i]&&j<=m;j++); 15 if(j>m)continue; 16 if(j!=i)for(k=1;k<=m;k++)swap(mp[j][k],mp[i][k]); 17 for(j=1;j<=m;j++)if(j!=i&&mp[j][i]) 18 for(k=1;k<=m;k++)mp[j][k]^=mp[i][k]; 19 } 20 // puts(""); 21 // for(i=1;i<=m;puts(""),i++)for(j=1;j<=m;j++)printf("%d ",mp[i][j]);puts(""); 22 } 23 24 int main(){ 25 scanf("%d%d",&n,&m); 26 for(i=1;i<=m;i++)f[0][i][i]=1;now=1;pre=0; 27 for(i=2;i<=n+1;i++,swap(now,pre)) 28 for(j=1;j<=m;j++) 29 for(k=1;k<=m;k++)f[now][j][k]^=f[pre][j-1][k]^f[pre][j][k]^f[pre][j+1][k]; 30 memcpy(mp,f[pre],sizeof(mp)); 31 gauss(); 32 for(i=m;i;i--) 33 if(!mp[i][i])ans[1][i]=1;else 34 for(j=i+1;j<=m;j++)if(mp[i][j])ans[1][i]^=ans[1][j]; 35 for(i=1;i<=n;i++){ 36 if(i>1) 37 for(j=1;j<=m;j++)ans[i][j]=ans[i-1][j]^ans[i-1][j-1]^ans[i-1][j+1]^ans[i-2][j]; 38 for(j=1;j<m;j++)printf("%d ",ans[i][j]);printf("%d ",ans[i][m]); 39 } 40 return 0; 41 }