都是水水的啦你们就别看了~~

[bzoj3503][Cqoi2014]和谐矩阵

听说没有题解

高斯消元解异或方程组

首先很容易想到如果知道第一行，那么剩下的每行就可以通过前两行得到了（第0行全为0）。同样，我们可以通过递推的方式得到第一行的数对后面每一行中的数的影响。。（偶数个1就是异或起来为0）

不妨令f[i][j]表示一个二进制数，其二进制下第k位表示第1行第k列的数对第i行第j列的数是否有影响，因为数只有0和1，所以有

f[1][i]=1<<(i-1), i∈[1, m]

f[i][j]=f[i-1][j-1] Xor f[i-1][j] Xor f[i-1][j+1] Xor f[i-2][j]，i∈[2, n], j∈[1, m]

递推计算出f之后，根据题意，有 f[i][j] Xor f[i][j-1] Xor f[i][j+1] Xor f[i-1][j] Xor f[i+1][j]=0

但是因为是递推的，前面n-1行显然成立，所以只要判断第n行是否可行就可以了。。

令p[i]=a[n][i] Xor a[n][i-1] Xor a[n][i+1] Xor a[n-1][i]，有：

{

(p[1]>>0 & 1)x[1] Xor (p[1]>>1 & 1)x[2] Xor (p[1]>>2 & 1)...Xor (p[1]>>(m-1) & 1)x[m]=0

(p[2]>>0 & 1)x[1] Xor (p[2]>>1 & 1)x[2] Xor (p[2]>>2 & 1)...Xor (p[2]>>(m-1) & 1)x[m]=0

...

(p[m]>>0 & 1)x[1] Xor (p[m]>>1 & 1)x[2] Xor (p[m]>>2 & 1)...Xor (p[m]>>(m-1) & 1)x[m]=0

}

即第一行每个数对第n行这个数的影响异或起来应该为0。。

其中x[i]表示第1行第i位的数字（0或1），那么接下来就是解这个不定方程了，高斯消元就可以了。。

消完之后发现全是0肯定是解，那么只能从自由元入手了。。

记a[i][j]为高斯消元后第j个方程x[i]前的系数, 那么如果a[i][i]=0，x[i]=1，然后再计算a[1..i][i]对x[i]的影响就可以了。。

P.s注意开long long。因为int特么只有32位而m<=40。。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Fill(x, Size, Num) fill(x+1, x+Size+1, Num)
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 45
typedef long long ll;
typedef pair<int, int> lnk;

ll f[Maxn][Maxn], Dlv[Maxn], a[Maxn][Maxn];
int n, m, equ, var, x[Maxn][Maxn], num[Maxn];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v, int w) { To[Cnt]=v; Len[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline int lcm(int x, int y) { return x*y/gcd(x, y); }
inline void Make_Equation(int Post) { for (int i=0; i<m; i++) a[Post][i]=((Dlv[Post+1]>>i)&1); }

inline void Get_Matrix()
{
	for (int i=2; i<=n; i++)
		for (int j=1; j<=m; j++) x[i][j]=x[i-1][j]^x[i-1][j-1]^x[i-1][j+1]^x[i-2][j];
	for (int i=1; i<=n; i++)
	{ for (int j=1; j<m; j++) printf("%d ", x[i][j]); printf("%d", x[i][m]); puts(""); }
}

inline int Gauss()
{
	int k, col;
	for (k=0, col=0; (k<equ) && (col<var); k++, col++)
	{
		int max_r=k;
		for (int i=k+1; i<equ; i++)
		{
			if (a[i][col]>a[max_r][col]) max_r=i;
			if (a[max_r][col]==1) break;
		}
		if (max_r^k) for (int i=col; i<=var; i++) swap(a[k][i], a[max_r][i]);
		if (!a[k][col]) { k--; continue; }
		for (int i=k+1; i<equ; i++)
			if (a[i][col])
				for (int j=col; j<=var; j++) a[i][j]^=a[k][j];
	}
}

int main()
{
	read(n); read(m);
	for (int i=1; i<=m; i++) f[1][i]=1ll<<(i-1);
	for (int i=2; i<=n; i++)
		for (int j=1; j<=m; j++)
			f[i][j]=f[i-1][j-1]^f[i-1][j]^f[i-1][j+1]^f[i-2][j];
	for (int i=1; i<=m; i++) Dlv[i]=f[n][i-1]^f[n][i]^f[n][i+1]^f[n-1][i];
	for (int i=0; i<m; i++) Make_Equation(i); equ=var=m;
	int Free_num=Gauss();
	for (int i=m-1; i>=0; i--)
	{
		if (!a[i][i]) x[1][i+1]=1;
		for (int j=0; j<i; j++) if (a[j][i]) x[1][j+1]^=x[1][i+1];
	}
	Get_Matrix();
}