ICPC济南A-Matrix Equation:高斯消元，异或线性方程
题目大意:
给你两个大小为 n n n的 01 01 01方阵 A , B A,B A,B.问你有多少个方阵 C C C满足 A ∗ C = B & C A*C=B\&C A∗C=B&C. ∗ 代 表 模 2 意 义 下 的 矩 阵 乘 法 , & 代 表 两 个 矩 阵 的 每 个 位 置 相 与 *代表模2意义下的矩阵乘法,\&代表两个矩阵的每个位置相与 ∗代表模2意义下的矩阵乘法,&代表两个矩阵的每个位置相与
n ≤ 200 n \leq 200 n≤200
题目思路:
不难对结果矩阵的每个位置 ( i , j ) (i,j) (i,j)列一个等式:
∑ i = 1 k A i , k C k , j ( m o d 2 ) = B i , j C i , j \sum_{i=1}^{k}A_{i,k}C_{k,j} \ \ (mod \ 2)=B_{i,j}C_{i,j} ∑i=1kAi,kCk,j (mod 2)=Bi,jCi,j
我们知道模二意义下的加法等于异或，那么推出:
⊕
i
=
1
k
A
i
,
k
C
k
,
j
=
B
i
,
j
C
i
,
j
\oplus_{i=1}^{k} A_{i,k}C_{k,j}=B_{i,j}C_{i,j}
⊕i=1kAi,kCk,j=Bi,jCi,j
进一步推出:
B
i
,
j
C
i
,
j
⊕
i
=
1
k
A
i
,
k
C
k
,
j
=
0
B_{i,j}C_{i,j}\oplus_{i=1}^{k} A_{i,k}C_{k,j}=0
Bi,jCi,j⊕i=1kAi,kCk,j=0
将 C i , j C_{i,j} Ci,j的系数合并得到:
A i , 1 C 1 , j ⊕ . . . ⊕ [ A i , i = = B i , j ] C i , j ⊕ . . . ⊕ A i , n C n , j = 0 − 式 ① A_{i,1}C_{1,j}\oplus ...\oplus [A_{i,i}==B_{i,j}]C_{i,j}\oplus ...\oplus A_{i,n}C_{n,j}=0\ \ -式① Ai,1C1,j⊕...⊕[Ai,i==Bi,j]Ci,j⊕...⊕Ai,nCn,j=0 −式①
至此，我们有 n 2 n^2 n2个方程, n 2 n^2 n2个未知数，所以显然有 O ( n 6 64 ) O(\frac{n^6}{64}) O(64n6)的高斯消元的做法，不可行.考虑进一步优化.
观察式子①:我们发现矩阵 C C C是列独立的。也就是说:对 C i , j C_{i,j} Ci,j列出的方程只会涉及到第 j j j列中的未知数 C r , j , r ∈ [ 1 , n ] C_{r,j},r \in[1,n] Cr,j,r∈[1,n]。不同列之间的元素没有共同的方程。那么我们可以按列计算，每一列的答案根据乘法原理相乘即可得到最终答案.
复杂度降到: O ( n 4 64 ) O(\frac{n^4}{64}) O(64n4). 可做.
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200 + 5;
const int mod = 998244353;
int f[maxn][maxn] , g[maxn][maxn];
ll ksm (ll a , ll b){ ll ans = 1 , base = a;
while (b){if (b & 1) ans = ans * base % mod;b >>= 1;base = base * base % mod;}return ans;}
bitset<maxn> a[maxn];
int n;
ll guess (int x)
{
// 计算系数
for (int i = 1 ; i <= n ; i++){
for (int j = 1 ; j <= n ; j++){
a[i][j] = f[i][j];
}
a[i][i] = (f[i][i] != g[i][x]);
}
// 跑高斯消元
int r , c , free = 0;
for (r = c = 1 ; r <= n && c <= n ; r++ , c++){
int p = 0;
for (int j = r ; j <= n ; j++){
if (a[j][c]){
p = j;
break;
}
}
if (!p){
r--;
free++;
continue;
}
swap(a[r] , a[p]);
for (int j = 1 ; j <= n ; j++){
if (j == r) continue;
if (a[j][c] == 0) continue;
a[j] ^= a[r];
}
}
return ksm(2 , free);
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1 ; i <= n ; i++)
for (int j = 1 ; j <= n ; j++)
cin >> f[i][j];
for (int i = 1 ; i <= n ; i++)
for (int j = 1 ; j <= n ; j++)
cin >> g[i][j];
ll ans = 1;
for (int i = 1 ; i <= n ; i++) ans = (ans * guess(i))%mod;
cout << ans << endl;
return 0;
}