第 45 届ICPC济南站 A.Matrix Equation异或高斯消元+求自由元+bitset优化

（异或高斯消元+求自由元+bitset优化）

具体模板可以看kuangbin

题意简述：

给定一个矩阵A,B，求满足A*C=B.C的矩阵C个数

*为矩阵乘法，.为矩阵点乘。

本题分析：

当能分析出高斯消元求解后，自然转化为一个模板题，重在如何发现是高斯消元

1. 对于只有01的运算操作：模2+/- 相当于 ^, *相当于&，而位运算包含一些结合律等性质，方便解题

2. 其次是对于矩阵乘法的理解：A*B，矩阵乘法行与列的运算次数为n^2，即无论是A的每一行还是B的每一列都会参与n次运算，这是列方程的关键

反思：当时试图利用整个矩阵乘法的性质求解，没有发现矩阵乘法中行，列之间的分离关系

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
bitset<210> a[210],b[210];
bitset<210> f[210];
int n;
ll qpow(ll x,ll p){
ll res=1;
while(p){
if(p&1) res=res*x%mod;
x=x*x%mod;
p>>=1;
}
return res;
}
int guess(){
int max_r,col,k;
int free=0;
for(k=0,col=0;k<n&&col<n;k++,col++){
max_r=k;
for(int i=k+1;i<n;i++){
if(abs(f[i][col])>abs(f[max_r][col])){
max_r=i;
}
}
if(f[max_r][col]==0){
k--;
free++;
continue;
}
if(max_r!=k){
swap(f[k],f[max_r]);
}
for(int i=k+1;i<n;i++){
if(f[i][col]){
f[i]^=f[k];
}
}
}
for(int i=k;i<n;i++){
if(f[i][col]) return -1;
}
return n-k;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x;
cin>>x;
a[i].set(j,x);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x;
cin>>x;
b[j].set(i,x);
}
}
int ans=0;
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
f[i]=a[i];
f[i].set(i,a[i][i]^b[k][i]);
}
int x=guess();
if(x==-1){
cout<<0<<"n";
}
ans+=x;
}
cout<<qpow(2,ans);
return 0;
}

最后

以上就是无心电话为你收集整理的第 45 届ICPC济南站 A.Matrix Equation异或高斯消元+求自由元+bitset优化的全部内容，希望文章能够帮你解决第 45 届ICPC济南站 A.Matrix Equation异或高斯消元+求自由元+bitset优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。