2020ICPC济南A Matrix Equation
∑ k = 1 n A i , k C k , j = B i , j C i , j → ⨁ k = 1 n A i , k C k , j = B i , j C i , j → B i , j C i , j ⊕ ( ⨁ k = 1 n A i , k C k , j ) = 0 → A i , 1 C 1 , j ⊕ A i , 2 C 2 , j ⊕ . . . ⊕ ( A i , i ⊕ B i , j ) C i , j ⊕ . . . ⊕ A i , n C n , j \sum_{k=1}^nA_{i,k}C_{k,j}=B_{i,j}C_{i,j}\rightarrow \bigoplus_{k=1}^nA_{i,k}C_{k,j}=B_{i,j}C_{i,j}\\ \rightarrow B_{i,j}C_{i,j}\oplus(\bigoplus_{k=1}^nA_{i,k}C_{k,j})=0\\ \rightarrow A_{i,1}C_{1,j}\oplus A_{i,2}C_{2,j}\oplus...\oplus(A_{i,i}\oplus B_{i,j})C_{i,j}\oplus...\oplus A_{i,n}C_{n,j} k=1∑nAi,kCk,j=Bi,jCi,j→k=1⨁nAi,kCk,j=Bi,jCi,j→Bi,jCi,j⊕(k=1⨁nAi,kCk,j)=0→Ai,1C1,j⊕Ai,2C2,j⊕...⊕(Ai,i⊕Bi,j)Ci,j⊕...⊕Ai,nCn,j
由此得到一个异或线性方程，对于一个固定的列
j
j
j，取
i
=
1
,
2
,
.
.
.
,
n
i={1,2,...,n}
i=1,2,...,n则得到一个异或线性方程组
T
j
T_j
Tj，从而
C
C
C的第
j
j
j列可以取的向量个数为
2
n
−
r
(
T
j
)
2^{n-r(T_j)}
2n−r(Tj)。答案为
∏
j
=
1
n
2
n
−
r
(
T
j
)
\prod\limits_{j=1}^n2^{n-r(T_j)}
j=1∏n2n−r(Tj)。
对于一个方程组，高斯消耗的复杂度为
O
(
n
3
)
O(n^3)
O(n3)，共有
n
n
n个方程组，总的时间复杂度为
O
(
n
4
)
O(n^4)
O(n4)，对于异或方程组，可以采用
b
i
t
s
e
t
bitset
bitset优化，从而时间复杂度为
O
(
n
4
/
w
)
O(n^4/w)
O(n4/w)。