3364 Lanterns (异或方程组高斯消元)

基本思路。首先构造一个n*(m+1)的矩阵，同时标记一个行数row，row从零开始，然后找出每一列第一个非零的数，和第row行互换，

然后对row到n行，异或运算。最终的结果为2^（m-row）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int array[55][55],n,m,h[55][55];
int main()
{
	int i,j,k,t,a,q;
	scanf("%d",&t);
	for(int v=1;v<=t;v++)
	{
		memset(array,0,sizeof(array));
		memset(h,0,sizeof(h));
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d",&k);
			while(k--)
			{
				scanf("%d",&a);
				array[a-1][i]=1;
			}
		}
		for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			h[i][j]=array[i][j];
		printf("Case %d:\n",v);
		scanf("%d",&q);
		while(q--)
		{
			for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				array[i][j]=h[i][j];
			for(i=0;i<n;i++)
				scanf("%d",&array[i][m]);
			/*for(i=0;i<n;i++)
			{
				for(j=0;j<=m;j++)
					printf("%d ",array[i][j]);
				printf("\n");
			}*/
			__int64 ans=1;
			int row=0;
			for(i=0;i<m;i++)
			{
				for(j=row;j<n;j++)
					if(array[j][i])
						break;
				if(j==n)continue;
				if(j!=row)
				{
					for(k=0;k<=m;k++)
						swap(array[row][k],array[j][k]);
				}
				for(j=row+1;j<n;j++)
				{
					if(array[j][i])
					{
						for(k=0;k<=m;k++)
							array[j][k]^=array[row][k];
					}
				}
				row++;//这里不用担心row超过n，因为从n行开始，每行的数字都是0
			}
				for(j=row;j<n;j++)
					if(array[j][m])
					{
						ans=0;
						break;
					}
				int tmp=m-row;
				while(tmp--)
					ans*=2;
			printf("%I64d\n",ans);
		}
	}
	return 0;
}

巴特西

3364 Lanterns (异或方程组高斯消元)

最新文章

热门文章