「CQOI2014」和谐矩阵 - 高斯消元解异或方程组 | Bill Yang's Blog

「CQOI2014」和谐矩阵 - 高斯消元解异或方程组

题目大意

    我们称一个有$0$和$1$组成的矩阵是和谐的,当且仅当每个元素都有偶数个相邻的$1$。
    一个元素相邻的元素包括它本身,以及他上下左右四个元素(如果存在)。
    给定矩阵的行数和列数,请计算并输出一个和谐的矩阵。请注意,所有元素为$0$的矩阵式不允许的。


题目分析

很和谐的一道题。

方法一

先考虑暴力的做法,根据题目的限制,不难根据周围的关系列出异或方程组(设$b,c,d,e$与$a$相邻):

根据这些限制,列出$n\times m$个方程,然后使用高斯消元解异或方程组。
时间复杂度$O((nm)^3)$。
使用bitset优化,将时间复杂度将为$O(\frac{(nm)^3}{64})$,可以通过。

注意,由于不能全选$0$,因此使用高斯约旦消元会很麻烦,改用高斯消元消成上三角矩阵后反代,自由元设置为$1$,由于题目保证有解,因此正确性显然。

方法二

由于:

使用$x-1$替换$x$得到:

也就是:

因此,$(x,y)$的值可以由前面的行的值完全确定下来,因此只需要确定第一行的值即可。
用一次状压递推,求出每个位置需要由哪些第一行的位置确定。
因为$n+1$行的值必定为$0$,因此就可以根据第一行的值列出异或方程组。

很神奇的方法,这样就只剩下$m$个方程组了,时间复杂度$O(m^3)$,用bitset优化后跑的飞起。


代码

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int dx[]= {0,1,-1,0,0},dy[]= {0,0,0,1,-1};

int n,m;
bool ans[1605];
bitset<1605> a[1605];

void Gauss(int n) {
for(int i=1; i<=n; i++) {
int row=i;
for(; row<=n; row++)if(a[row][i])break;
if(row>n)continue;
swap(a[i],a[row]);
for(int j=i+1; j<=n; j++)if(j!=i&&a[j][i])a[j]^=a[i];
}
for(int i=n; i>=1; i--) {
ans[i]=a[i][i]?a[i][n+1]:1;
if(ans[i])for(int j=1; j<i; j++)if(a[j][i])a[j].flip(n+1);
}
}

int id(int x,int y) {return (x-1)*m+y;}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=0; k<=4; k++) {
int nx=i+dx[k],ny=j+dy[k];
if(nx<1||ny<1||nx>n||ny>m)continue;
a[id(i,j)][id(nx,ny)]=1;
}
Gauss(n*m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)printf("%d%c",ans[id(i,j)],j==m?'\n':' ');
return 0;
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

int n,m;
bool ans[45][45];
bitset<45> a[45],b[45][45];

void Gauss(int n) {
for(int i=1; i<=n; i++) {
int row=i;
for(; row<=n; row++)if(a[row][i])break;
if(row>n)continue;
swap(a[i],a[row]);
for(int j=i+1; j<=n; j++)if(a[j][i])a[j]^=a[i];
}
for(int i=n; i>=1; i--) {
ans[1][i]=a[i][i]?a[i][n+1]:1;
if(ans[1][i])for(int j=1; j<i; j++)if(a[j][i])a[j].flip(n+1);
}
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++)b[1][i][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++)a[i]=b[n+1][i];
Gauss(m);
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%c",ans[i][j],j==m?'\n':' ');
return 0;
}

姥爷们赏瓶冰阔落吧~
0%