【JZOJ5553】【20190625】谜

题目

给出一个\(２\times n\)个点的二分图的邻接矩阵\(M\)

以及\(m\)个行替换元，\(k\)个列替换元

\(q\)次询问：op u v 表示用第v个行/列替换元去替换矩阵的第u行/列

对初始以及每个操作矩阵输出完全匹配的方案数mod 2 的值

\(n ,m,k \le 10^3 \ , \ q \le 10^5\)

题解

在mod 2 的意义下-1=1，所以完全匹配的方案数=\(det(M)\)
bitset 暴力高斯消元\(O(q\frac{n^3}{\omega})\)
询问相当于每次替换一个行或者列，询问矩阵是否满秩
考虑预处理出所有询问的答案
由于替换某一行或者列最多使矩阵的秩加减1
1.如果原矩阵的秩为\(n\):

由于矩阵满秩，那么对于每一个\(n\)阶向量都可以被线性表示；

对于每一个询问预处理出这样的表示，可以替换的就是系数为1的位置　
2.如果原矩阵的秩为\(n-1\):

一定存在并且仅存在一组线性相关的向量，它们的异或和为0向量

在原来\(n\)个向量中，任意去掉其中的一个都是一个线性无关的组

对原矩阵消元得到一个基，对一个询问能被线性表出，那么无论如何替换一定不满秩

否则出现了一个\(n　\)个向量的线性无关组，可以替换的就是最开始存在的线性相关那组向量中的任意一个
时间复杂度：\(O(\frac{n^3}{\omega})\)

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

typedef bitset<1010> Bit;

int n;

char s[N];

Bit a[N],b[N],p[N],q[N],c,ans[2][100000];

int gauss(Bit*A,Bit*B){

	int i=1,j=1;

	for(;i<=n&&j<=n;++i,++j){

		int pos=i;while(pos<=n&&!A[pos][j])++pos;

		if(pos>n){i--;continue;}

		if(i!=pos)swap(A[i],A[pos]),swap(B[i],B[pos]);

		for(int k=i+1;k<=n;++k)if(A[k][j])A[k]^=A[i],B[k]^=B[i];

	}

	return i<n?0:i==n?2:1;

}

void get(int fg,Bit*A,Bit*B,Bit C,Bit&re){

	int i=1,j=1,pos=0;

	for(;i<=n&&j<=n;++i,++j){

		if(!A[i][j]){pos=j,i--;continue;}

		if(C[j])C^=A[i],re^=B[i];

	}

	if(fg==2){

		if(C.test(pos))re=B[n];

		else re.reset();

	}

}

int main(){

	freopen("maze.in","r",stdin);

	freopen("maze.out","w",stdout);

	int m,k,Q;scanf("%d",&n);

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

		scanf("%s",s+1);p[i].set(i);q[i].set(i);

		for(int j=1;j<=n;++j)if(s[j]=='1')a[i].set(j),b[j].set(i);

	}

	int fg=gauss(a,p);gauss(b,q);

	//printf("%d:\n",fg);

	scanf("%d%d",&m,&k);

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

		scanf("%s",s+1);c.reset();

		for(int j=1;j<=n;++j)if(s[j]=='1')c.set(j);

		if(!fg)continue;

		get(fg,a,p,c,ans[0][i]);

	}

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

		scanf("%s",s+1);c.reset();

		for(int j=1;j<=n;++j)if(s[j]=='1')c.set(j);

		if(!fg)continue;

		get(fg,b,q,c,ans[1][i]);

	}

	puts(fg&1?"1":"0");

	scanf("%d",&Q);

	for(int i=1,op,u,v;i<=Q;++i){

		scanf("%d%d%d",&op,&u,&v);

		printf("%d\n",ans[op][v].test(u));

	}

	return 0;

}

巴特西

【JZOJ5553】【20190625】谜

题目

题解

最新文章

热门文章