Tag-高斯消元

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

 2021-01-15 19:36:41 |  0 Comments  |  bitset 高斯消元

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

题目大意

求矩阵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){
 2020-04-16 21:31:39 |  0 Comments  |  高斯消元 bitset

2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest I . Infinite Gift

题目大意

给出n个k维向量vi,对于k维空间中所有点a,将点a与点a+vi连边,求问全部连接完的图能否完成黑白染色。

题解

黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。

考虑二分图形成的条件:不能出现奇环。

于是问题就转变成了如何判断图中是否会存在奇环。

但是这个题目明显不能用通常的搜索判环解决。

考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。

假设n个未知数xi,假设一个点想要回到自身,需要使用第i个向量xi次。

于是要形成环即向量方程:

x1v1 + x2v2 + ... + xnvn = 0有解。

所以如果要保证形成奇数环的话,就是加入以下一个方程

xxor x2 xor ... xor xn = 1

联立来解一个n元k+1维方程组。

将上面的向量方程拆分到k维k个方程,并将所有运算全都mod 2处理,即可让整个方程组变成一个异或方程组。

能形成二分图的条件就是方程组不存在解,否则就说明构成的图不是二分图。

使用高斯消元解决方程组判断解的问题。

但是高斯消元有一个问题,就是复杂度不对,为O(nk2)

不过由于这道题的方程组的运算只与二进制异或有关,所以可以把方程的参数放入bitset加速,最终复杂度为O(nk2/64)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
bitset<maxn>g[maxn];
int n,k,now,x;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= k;++j){
            cin >> x;
            g[j][i] = abs(x) % 2;
        }
    }
    for(int i = 1;i <= n+1;++i){
        g[k+1][i] = 1;
    }
    now = 0;
    for(int i = 1;i <= n;++i){
        int j
Title - Artist
0:00