2020ICPC 济南site A Matrix Equation bitset + 异或高斯消元

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

求矩阵C的个数,满足A×C = B·C。其中×表示矩阵乘(模数为2,也即矩阵的异或乘),·表示矩阵元素与。

题解

博主在正式赛的时候执着于找规律,最后才看到高斯消元,所以最后就白给了,拿了个铜滚粗了。

其实没必要去算什么规律的,我们直接设C的元素为c11 ……cnn,然后直接按照两种操作的定义展开即可。

之后我们可以发现c中的元素的每一列都构成了一组n元的异或方程组,而不同列之间的元素是没有相互影响的。这样我们就可以应用高斯消元,求解自由元的个数,计算出每一列自由元个数xi,最后结果就是Πxi。算法的总复杂度是O(n4)的

但是这个题目的数据是N ≤ 200,所以算法O(n4)的时间复杂度是无法接受的,但是我们又无法做到在指数级上进行优化,所以考虑常数优化。考虑到异或方程组的行间计算实际上都是异或操作,所以我们可以考虑用bitset代替自己写的数组式矩阵。这样最终算法的时间复杂度为O(n4/64)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll quick_pow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y & 1)
			res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
const int maxn = 205;
int a[maxn][maxn],b[maxn][maxn];
bitset<maxn>bs[maxn],bd[maxn],t;
int n;
ll ans;
void swap(bitset<maxn> &x,bitset<maxn> &y){
	t.reset();
	t |= y;
	y.reset();
	y |= x;
	x.reset();
	x |= t;
	return;
}
int Guass(){
	int maxrow,row = 0,col = 0,num = 0;
	for(row = 0;row < n && col < n;row++,col++){
		maxrow = row;
		for(int i = row + 1;i < n;++i){
			if(bd[i][col] > bd[maxrow][col]){
				maxrow = i;
				break;
			}
		}
		if(maxrow != row){
			swap(bd[maxrow],bd[row]);
		}
		if(bd[row][col] == 0){
			num++;
			row--;
			continue;
		}
		for(int i = row + 1;i < n;++i){
			if(bd[i][col] != 0){
				bd[i] ^= bd[row];
			}
		}
	}
	return num;
}
void solve(int x){
	for(int i = 0;i < n;++i)
		bd[i].reset();
	for(int i = 0;i < n;++i){
		bd[i] |= bs[i];
		bd[i][i] = b[i][x] ^ bd[i][i];
	}
	int num = Guass();
	if(num == -1){
		ans = 0;
	}
	else ans = ans * quick_pow(2,num) % mod;
}
int main(){
	cin >> n;
	ans = 1;
	for(int i = 0;i < n;++i)
		bs[i].reset();
	for(int i = 0;i < n;++i)
		for(int j = 0;j < n;++j)
			cin >> a[i][j],bs[i].set(j,a[i][j] == 1);
	for(int i = 0;i < n;++i)
		for(int j = 0;j < n;++j)
			cin >> b[i][j];
	for(int i = 0;i < n;++i){
		solve(i);
	}
	cout << ans << endl;
	return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00