传送门

垃圾题面,毁我青春好吧其实是我眼瞎qwq。。。

显然题目可以转化成一个模$2$意义下的行列式(其实是积和式,但是模$2$所以积和式等于行列式),每次把其中一个$1$变成$0$,问剩下的行列式。不难发现其实就是在问每个$1$的余子式。

一开始没看到保证行列式不为0,想了半天根本不会做,结果弃疗去看题解之后才发现看漏了。。。

可逆就能随便做了,直接求个逆,然后转置一下得到伴随矩阵然后就得到每个位置的余子式了。

然而不保证可逆的情况下怎么做啊,还是不会啊QAQ

哪位dalao会做的话请务必联系我qwq

#include <bits/stdc++.h>
#define MAXN 2010
using namespace std;

int n,m;
bitset<MAXN> a[MAXN],b[MAXN],temp;
int e[500010][2];

void gao(){
    for(int i=1;i<=n;i++){
        int pos=0;
        for(int j=i;j<=n;j++)
            if(a[j][i]) pos=j;
        if(i^pos){
            temp=a[pos];
            a[pos]=a[i];
            a[i]=temp;
            temp=b[pos];
            b[pos]=b[i];
            b[i]=temp;
        }
        for(int j=1;j<=n;j++)
            if(i!=j && a[j][i]){
                a[j]=a[j]^a[i];
                b[j]=b[j]^b[i];
            }
    }
}

int main(){
#ifdef DEBUG
    freopen("128.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[x][y]^1;
        e[i][0]=x; e[i][1]=y;
    }
    for(int i=1;i<=n;i++) b[i][i]=1;
    gao();
    for(int i=1;i<=m;i++){
        if(b[e[i][1]][e[i][0]]) puts("NO");
        else puts("YES");
    }
    return 0;
}