题目链接

HDU3915 Game 高斯消元

题解

求异或方程组*元的子集个数

高斯消元求秩,内存溢出好神

代码

#include<bitset>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std ;

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' ||c > '9'){if(c == '-') f = -1;c = getchar();}

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

	return x * f;

}

bitset<105>a[32];

int n;

void gauss(int equ ,int var) {

	int r , c , t ;

	for(r = c = 1;r <= equ && c <= var;++ r ,++ c) {

		t = r;

		for(;t < equ;++ t) if(a[t][c]) break ;

		if(t == equ) {

			-- r ;continue ;

		} else swap(a[t] , a[r]);

		for(int i = r + 1;i <= equ;++ i) if (a[i][c]) a[i] ^= a[r];

	}

	int n = var - r , ans = 1;

	for(int i = 1;i <= n;++ i) {

		ans <<= 1 ;ans %= 1000007;

	}

	printf("%d\n",ans);

}

int main () {

	int T = read();

	while(T --) {

		for(int i = 1;i <= 31; ++ i) a[i] = 0;

		n = read();

		for(int x,i = 1;i <= n;++ i) {

			x = read();

			for(int j = 1;j <= 31;++ j) a[j][i] = ((x >> j) & 1);//,printf("%d\n",n);

		}

		gauss(31,n);

	}

	return 0 ;

}