開關問題 高斯消元 異或方程組

開關問題

思路

高斯消元，異或方程組。把增廣矩陣的每一行進行你狀态壓縮，用一個Int類型的數組表示增廣矩陣，數組中每個元素表示n+1位二進制數，第0位為增廣矩陣最後一列常數，第1~n位分别表示增廣矩陣第1到n列的系數。

code

#include<bits/stdc++.h>
using namespace std;
int a[100],ans;
int n;
int main()
{
	int t;
	cin>>t;
	while(t--)
    {
		cin>>n;
		for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
		for(int i=1,j;i<=n;i++)
		{
			scanf("%d",&j);
			a[i]^=j;
			a[i]|=1<<i;///a[i][i] = 1
		}
		int x,y;
		while(~scanf("%d%d",&x,&y)&&x&&y)
		{
			a[y]|=1<<x;///a[y][x] = 1
		}
		ans=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(a[j]>a[i])
                    swap(a[j],a[i]);
			}
			if(a[i]==0)
			{
				ans=1<<(n-i+1);
				break;
			}
			if(a[i]==1)
			{
				ans=0;
				break;
			}
			for(int k=n;k;k--)
			{
				if(a[i]>>k&1)///如果a[i]的第k位為1
				{
					for(int j=1;j<=n;j++)
					{
						if(i!=j&&a[j]>>k&1)///i不等于j，且a[j]的第k位為1
                            a[j]^=a[i];///将a[j]的第k位置為0
					}
					break;
				}
			}
		}
		if(!ans)
            puts("Oh,it's impossible~!!");
		else
            printf("%d\n",ans);
	}
	return 0;
}