bzoj3503:[Cqoi2014]和谐矩阵(高斯消元)

题解

  第一次写高斯消元解异或方程组的题,各种出小偏差…
  首先有一种比较显然的做法,对于每一个点上下左右和自己xorxor后为00,那么我们可以列出n×mn\times m个异或方程组,高斯消元后就能得出答案了,复杂度O((n×m)3)O((n\times m)^3)
  还有一种比较喵喵的写法。确定了第一行之后这个矩阵就确定了,因为ai,j=ai1,j xor ai1,j1 xor ai1,j+1 xor ai2,ja_{i,j}=a_{i-1, j}\ xor\ a_{i-1,j-1}\ xor\ a_{i-1, j+1}\ xor\ a_{i-2, j}。一个矩阵是和谐矩阵可以得到第m+1m+1行全为00
  因为某一行可以确定下一行,那么我们可以用第11行来表示第m+1m+1行,并且我们知道m+1m+1行全为00,那么就可以高斯消元得到答案了。
  异或方程组的高斯消元和普通高斯消元还是有点差别的,当作存板子吧。需要注意的是自由元要设为11,否则可能出现有解但是矩阵全00的情况。还有因为自由元的原因,高斯消元完可能有一些方程还是有多个为11的系数,这时候就需要手动异或掉把它变成0了,并且需要倒着异或因为第ii行出现为11的系数的下标一定i\geq i

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<vector>
#include<algorithm> 
using namespace std;
const int maxn=50;
int n, m;
long long a[maxn][maxn], b[maxn][maxn], ans[maxn][maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline bool gauss()
{
    int to, now=1; int x;
    for(int i=1;i<=m;i++)
    {
        for(to=now;to<=m;to++) if(a[to][i]) break;
        if(to>m) continue;
        if(to!=now) for(int j=1;j<=m+1;j++) swap(a[to][j], a[now][j]);
        x=a[now][i]; if(!x) for(int j=1;j<=m+1;j++) a[now][j]^=1;
        for(int j=1;j<=m;j++)	
        if(now!=j && a[j][i])
        for(int k=1;k<=m+1;k++)
        a[j][k]^=a[now][k];
        now++;
    }
    return now>m; 
}
int main()
{
	scanf("%d%d", &n, &m); 
	for(int i=1;i<=m;i++) b[1][i]=1ll<<(i-1);
	for(int i=2;i<=n+1;i++) for(int j=1;j<=m;j++) 
	b[i][j]=b[i-1][j-1]^b[i-1][j]^b[i-1][j+1]^b[i-2][j];
	for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) a[i][j]=(b[n+1][i]>>(j-1))&1;
	gauss();
	for(int i=1;i<=m;i++) ans[1][i]=a[i][i]?a[i][m+1]:1;
	for(int i=m;i;i--)
    if(!a[i][i]) ans[1][i]=1;
	else for(int j=i+1;j<=m;j++) if(a[i][j]) ans[1][i]^=ans[1][j];
	for(int i=2;i<=n;i++) for(int j=1;j<=m;j++) 
	ans[i][j]=ans[i-1][j-1]^ans[i-1][j]^ans[i-1][j+1]^ans[i-2][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<m;j++) printf("%d ", ans[i][j]);
		printf("%d\n", ans[i][m]);
	}
}

  实际上用bitset可以优化高斯消元异或方程组,就能过100010001000*1000的方程组了…贴一下bzoj19231923的代码…

bzoj19231923代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<bitset>
#include<algorithm> 
using namespace std;
const int maxn=1010;
int n, m, x, ans;
bitset<maxn>a[maxn<<1];
char s[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline int gauss()
{
    int to, now=1; int x;
    for(int i=1;i<=n;i++)
    {
        for(to=now;to<=m;to++) if(a[to][i]) break;
        if(to>m) continue;
        ans=max(ans, to);
        if(to!=now) swap(a[to], a[now]);
		x=a[now][i]; if(!x) a[now]^=1;
        for(int j=1;j<=m;j++)	
        if(now!=j && a[j][i]) a[j]^=a[now];
        now++;
    }
    return now>n; 
}
int main()
{
	read(n); read(m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s", s+1); read(x); a[i][n+1]=x&1;
		for(int j=1;j<=n;j++) a[i][j]=(s[j]-'0');
	}
	if(!gauss()) return puts("Cannot Determine"), 0;
	printf("%d\n", ans);	
	for(int i=1;i<=n;i++) printf("%s\n", a[i][n+1]?"?y7M#":"Earth");
}