[POJ1830]开关问题(高斯消元,异或方程组)

题目链接:http://poj.org/problem?id=1830

题意:中文题面,求的是方案数。

首先可以知道, 如果方案数不止一个的话,说明矩阵行列式值为0,即存在*变元,由于变量只有两种状态,那么方案数就是2^*变元数。

从起始状态到终止状态,只需要关心起始和终止哪些状态不一样就行,也就是翻转奇数次。

由于是倒推,所以开关的影响要反过来存。

 #include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
int equ, var;
int a[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num; int gauss() {
int max_r, col, k;
free_num = ;
for(k = , col = ; k < equ && col < var; k++, col++) {
max_r = k;
for(int i = k + ; i < equ; i++) {
if(abs(a[i][col]) > abs(a[max_r][col]))
max_r = i;
}
if(a[max_r][col] == ) {
k--;
free_x[free_num++] = col;
continue;
}
if(max_r != k) {
for(int j = col; j < var + ; j++)
swap(a[k][j], a[max_r][j]);
}
for(int i = k + ; i < equ; i++) {
if(a[i][col] != ) {
for(int j = col; j < var + ; j++) {
a[i][j] ^= a[k][j];
}
}
}
}
for(int i = k; i < equ; i++) {
if(a[i][col] != )
return -;
}
if(k < var) return var - k;
for(int i = var - ; i >= ; i--) {
x[i] = a[i][var];
for(int j = i + ; j < var; j++) {
x[i] ^= (a[i][j] & x[j]);
}
}
return ;
} int main() {
// freopen("in", "r", stdin);
int T, _ = ;
char wtf[] = "Oh,it's impossible~!!";
scanf("%d", &T);
while(T--) {
scanf("%d", &var);
equ = var;
memset(a, , sizeof(a));
memset(x, , sizeof(x));
memset(free_x, , sizeof(free_x));
for(int i = ; i < var; i++) {
scanf("%d", &a[i][var]);
a[i][i] = ;
}
int u, v;
for(int i = ; i < var; i++) {
scanf("%d", &u);
a[i][var] ^= u;
}
while(~scanf("%d%d",&u,&v) && u+v) {
a[v-][u-] = ;
}
int ret = gauss();
if(ret == -) puts(wtf);
else printf("%lld\n", (LL)((LL) << ret));
}
return ;
}
上一篇:微信web开发者工具初探


下一篇:Fzu月赛11 老S的旅行计划 dij