1830.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"vector"
#include"algorithm"
#include"iostream"
using namespace std;
int jie(vector< vector<int> > &a)
{int n=a.size();
 int i,j,k,t,l;
 for(i=0,l=0;i<n&&l<n;i++,l++)
 {	
	 do{
	for(j=i+1;j<n;j++)
	{
		if(a[i][l]==0)swap(a[i],a[j]);
		else break;
	}	
	if(j==n)l++;	 
	 }while(j==n&&l<n);	 
	if(l==n)break;	
	for(j=i+1;j<n;j++)
		if(a[j][l])
		{t=a[j][l];
			for(k=l;k<n+1;k++)a[j][k]^=a[i][k];
		}

}
int an;
for(i=0;i<n;i++)
for(j=0;j<=n;j++)
{a[i][j]%=2; 
a[i][j]+=2;
a[i][j]%=2;
}
for(an=0,i=n-1;i>=0;i--)
	if(find(a[i].begin(),a[i].end()-1,1)==a[i].end()-1)
		{if(a[i][n]!=0)return -1;
		 else an++;
		}
return an;
}
int main()
{vector< vector<int> > a;
 vector<int> b;
int k,n,i,j,c,d;
cin>>k;
while(k--)
	{a.clear();b.clear();
	cin>>n;
	a.resize(n);b.resize(n);
	for(i=0;i<n;i++)a[i].resize(n+1);
	for(i=0;i<n;i++)cin>>b[i];
	for(i=0;i<n;i++)
	{	
		cin>>c;
		if(c==b[i])a[i][n]=0;
		else a[i][n]=1;
	}
	for(i=0;i<n;i++)
	{	for(j=0;j<n;j++)a[i][j]=0;
		a[i][i]=1;
	}	
	for(cin>>c>>d;c!=0||d!=0;cin>>c>>d)
	{	a[d-1][c-1]=1;}
/*	
	for(i=0;i<n;i++)
	{for(j=0;j<=n;j++)cout<<a[i][j]<<' ';
	cout<<endl;
	}
	cout<<endl;
*/
	d=jie(a);
/*	

	for(i=0;i<n;i++)
	{for(j=0;j<=n;j++)cout<<a[i][j]<<' ';
	cout<<endl;
	}
*/						
	if(d<0)cout<<"Oh,it's impossible~!!"<<endl;
	else {long an;
		for(an=1;d--;an*=2);
		
		cout<<an<<endl;
	}

}
return 0;
}