Description

你要生成一个长度为$n$的排列,有$m$个可行数对,每个可行数对形如'$b_i$这个数可以放在第$a_i$个位置上’。现在你知道通过这$m$个可行数对能够生成出来的排列的数量是奇数,对于每个可行数对,你想知道:如果把这个可行数对删掉,那么能够生成的排列的数量是否还是奇数.

Input

$n\ m$

$a_i\ b_i$

$n \le 2 \times 10^3, m \le 5 \times 10^5$

Output

输出$m$行,如果把第$i$个可行数对去掉之后能够生成的排列数为奇数,第$i$行输出YES,否则输出NO.

Solution

题目问的就是:给出一个二分图,它的完美匹配方案数为奇数.问删去二分图的每一条边后,完美匹配数是否仍为奇数.

如何刻画一个二分图的完美匹配数?考虑它的邻接矩阵$A$,如果左边第$i$个点与右边第$j$个点有连边,那么$A_{i, j} = 1$, 否则为$0$.二分图的完美匹配数就是这个矩阵的积和式(permanent),它的定义与行列式类似, 唯一的区别是行列式中每一项还需要乘上$-1$的对应排列逆序对个数次方:

计算积和式是一个经典的NP问题,它的最优秀的算法也需要$O(2^{n - 1}n)$时间.

但是本题中我们只需要知道它的奇偶性,不难发现,它的奇偶性与行列式的奇偶性相同($a \equiv -a (\text{mod } 2)$).

这样问题就变成了求在将某个元素$A_{i, j}$的值变为$0$后,剩下的矩阵的行列式的奇偶性.根据行列式定义可以发现,此时行列式减小的值就是对应元素的代数余子式$M_{i, j}$的值.($M$的转置是$A$的伴随矩阵)

我们需要对每个元素都求一遍,快速的方法是将伴随矩阵求出来,根据定义:

这样我们我们只需要求矩阵的逆,因为题目保证一开始的完美匹配数为奇数,所以矩阵必定可逆.

由于是$0/1$矩阵,高斯消元时可使用$bitset$优化,复杂度为$O(\frac{n^3}{\omega} + m)$

Source

#include <bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

const int N = 2010, M = 500010;

bitset<N> A[N], B[N];
pair<int, int> E[M];
int n, m;

int main(){
	
	scanf("%d%d", &n, &m);
	For(i, 1, m){
		int u, v;
		scanf("%d%d", &u, &v);
		A[u][v] = 1;
		E[i] = make_pair(u, v);
	}
	For(i, 1, n) B[i][i] = 1;

	For(i, 1, n){
		int k = i;
		For(j, i, n) if(A[j][i]){
			k = j; break;
		}
		swap(A[i], A[k]), swap(B[i], B[k]);
		For(j, 1, n) if(i != j && A[j][i]) A[j] ^= A[i], B[j] ^= B[i];
	}

	For(i, 1, m) puts(B[E[i].second][E[i].first] ? "NO" : "YES");
	
	return 0;
}