题目链接
题目：
定义两种矩阵运算：
（1）
Z
=
X
×
Y
Z=X times Y
Z=X×Y，即
Z
i
,
j
=
(
∑
k
=
1
N
X
i
,
k
Y
k
,
j
)
m
o
d
2
Z_{i,j}=(sum_{k=1}^N X_{i,k}Y_{k,j}) mod 2
Zi,j=(∑k=1NXi,kYk,j)mod2
（2）
Z
=
X
⊙
Y
Z=X odot Y
Z=X⊙Y，即
Z
i
,
j
=
X
i
,
j
Y
i
,
j
Z_{i,j}=X_{i,j}Y{i,j}
Zi,j=Xi,jYi,j
给定两个
n
×
n
n times n
n×n的01矩阵
A
,
B
A,B
A,B，问有多少个
n
×
n
n times n
n×n的01矩阵
C
C
C满足
A
×
C
=
A
⊙
C
A times C=A odot C
A×C=A⊙C。
(
1
≤
n
≤
200
,
A
i
,
j
,
B
i
,
j
∈
{
0
,
1
}
)
(1 le n le 200,A_{i,j},B_{i,j} in {0,1})
(1≤n≤200,Ai,j,Bi,j∈{0,1})
题解：
首先可以发现
C
C
C的列与列之间是没有关系的，所以我们可以单独地求解每一列的数量，然后用乘法原理合并答案。将
C
C
C的第
k
k
k列看成
n
n
n维向量，我们就可以得到以下方程组
(
A
i
,
1
C
1
,
k
+
A
i
,
2
C
2
,
k
+
.
.
.
+
A
i
,
n
C
n
,
k
)
m
o
d
2
=
B
i
,
k
C
i
,
k
,
1
≤
i
≤
n
(A_{i,1}C_{1,k}+A_{i,2}C_{2,k}+...+A_{i,n}C_{n,k})mod 2=B_{i,k}C_{i,k},1 le i le n
(Ai,1C1,k+Ai,2C2,k+...+Ai,nCn,k)mod2=Bi,kCi,k,1≤i≤n
因为矩阵
A
A
A是01矩阵，又是模2意义下的加法，即异或运算，所以可以把上述方程组变成异或方程组。如
A
1
,
∙
=
(
1
,
0
,
1
,
1
)
,
C
∙
,
k
=
(
x
1
,
x
2
,
x
3
,
x
4
)
T
,
B
1
,
k
=
1
A_{1,bullet}=(1,0,1,1),C_{bullet,k}=(x1,x2,x3,x4)^T,B_{1,k}=1
A1,∙=(1,0,1,1),C∙,k=(x1,x2,x3,x4)T,B1,k=1，
那么可以得到
(
x
1
+
x
3
+
x
4
)
m
o
d
2
=
x
1
x
1
⊕
x
3
⊕
x
4
=
x
1
x
3
⊕
x
4
=
0
(x1+x3+x4)mod2=x1\ x1 oplus x3 oplus x4=x1\ x3 oplus x4=0
(x1+x3+x4)mod2=x1x1⊕x3⊕x4=x1x3⊕x4=0
所以最后可以得到一个齐次的异或方程组，那么问题就转化为了这个方程组有多少个解，那么可以求出异或空间里系数矩阵的秩
r
k
r_k
rk，那么自由元的数量为
n
−
r
k
n-r_k
n−rk，因为取值只有0,1，所以解的个数为
2
n
−
r
k
2^{n-r_k}
2n−rk，那么最后的答案就是
∏
k
=
1
n
2
n
−
r
k
prod_{k=1}^n 2^{n-r_k}
∏k=1n2n−rk。关于怎么求秩，可以用异或高斯消元，也可以通过将矩阵的行向量插入线性基得到极大线性无关组来求，两种方法的复杂度都是
O
(
n
4
)
O(n^4)
O(n4)的，过不了这道题，这里考虑用
b
i
t
s
e
t
bitset
bitset来存储行向量进行优化，复杂度降为
O
(
n
4
/
ω
)
O(n^4/omega)
O(n4/ω)。（用高斯消元求秩的时候有个坑点，行和列要用两个指针指，因为遇到一个自由元后，行指针不变，列指针要右移一个位置）
复杂度： O ( n 4 / ω ) O(n^4/omega) O(n4/ω)
代码：
1、高斯消元版
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<bitset> #include<sstream> #include<ctime> //#include<chrono> //#include<random> //#include<unordered_map> using namespace std; #define ll long long #define ls o<<1 #define rs o<<1|1 #define pii pair<int,int> #define fi first #define se second #define pb push_back #define mp make_pair #define sz(x) (int)(x).size() #define all(x) (x).begin(),(x).end() const double pi=acos(-1.0); const double eps=1e-6; const int mod=998244353; const int INF=0x3f3f3f3f; const int maxn=205; ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; bitset<maxn>a[maxn]; int ans[maxn]; int A[maxn][maxn],B[maxn][maxn]; int guass(int n){ int res=0; for(int i=1,p=1;i<=n;i++){ int m=p; if(!a[m][i]){ for(int j=p+1;j<=n;j++){ if(a[j][i]){ m=j; break; } } } if(!a[m][i]){ continue; } if(p!=m)swap(a[p],a[m]); for(int j=p+1;j<=n;j++){ if(a[j][i]){ a[j]^=a[p]; } } ++res; p++; } return res; } int qpow(int a,int p){ int res=1; while(p){ if(p&1)res=1ll*res*a%mod; a=1ll*a*a%mod; p>>=1; } return res; } int main(void){ // freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&A[i][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&B[i][j]); } } int ans=0; for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=A[i][j]; } if(B[i][k])a[i][i]=a[i][i]^1; } ans+=n-guass(n); } printf("%dn",qpow(2,ans)); return 0; }
2、线性基版（比赛中写的，码风不大对劲）
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#include<bits/stdc++.h> #include<bitset> using namespace std; const int maxn=205; typedef long long ll; const ll mod=998244353; struct L{ bitset<210>a[210]; int maxl; void init(int n){ maxl=n; for(int i=0;i<=n;i++){ a[i].reset(); } } int ins(bitset<210>t){ for(int i=maxl;i>=0;i--){ if(t[i]==0)continue; if(a[i].any())t^=a[i]; else{ for(int j=0;j<i;j++){ if(t[j]==1)t^=a[j]; } for(int j=i+1;j<=maxl;j++){ if(a[j][i])a[j]^=t; } a[i]=t; break; } } if(t.any())return 1; else return 0; } }L; ll qpow(ll a,ll p){ ll res=1; while(p){ if(p&1)res=res*a%mod; a=a*a%mod; p>>=1; } return res; } int n; int a[maxn][maxn],b[maxn][maxn]; void solve() { scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&b[i][j]); } } bitset<210>bt; ll ans=1; for(int k=1;k<=n;k++){ L.init(n); int cnt=n; for(int i=1;i<=n;i++){ bt.reset(); for(int j=1;j<=n;j++){ if(a[i][j])bt.set(j-1); } if(b[i][k])bt.flip(i-1); cnt-=L.ins(bt); } ans*=qpow(2,cnt); ans%=mod; } printf("%lldn",ans%mod); } int main() { int T=1; // scanf("%d",&T); for(int t=1;t<=T;t++) { solve(); } return 0; }
最后
以上就是听话盼望最近收集整理的关于2020ICPC济南A Matrix Equation的全部内容，更多相关2020ICPC济南A内容请搜索靠谱客的其他文章。
发表评论 取消回复