当前位置：首页 > news >正文

异或高斯消元模板（板子整理）

news 来源：原创 2024/9/20 22:24:18

板子整理

// 异或高斯消元模板
int gauss(int n)//n*n矩阵，返回0表示有唯一解，r<n表示有无穷多组解(n-r个自由元)，-1表示无解
{int r, c;//分别表示行、列for (r = 0, c = 0; c < n; c++){//第一步：找出第c列中为1的任意一行int t = r;for (int i = r; i < n; i++)if (a[i][c]) { t = i; break; }if (!a[t][c]) continue;//如果所有方程的这一列都为0那么不进行操作//第二步：将这一行换至第一行(未确定方程的第一行)，即第r行for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);//第三步：将这一行之后的每一行的第c列的数变成0for (int i = r + 1; i < n; i++)if (a[i][c])for (int j = c; j <= n; j++)a[i][j] ^= a[r][j];r++;//处理完当前行，进入下一行}if (r < n){for (int i = r; i < n; i++)if (a[i][n]) return -1;  // 无穷多解，但这里还是令自由元都为0，解出一组解return n-r;}for (int i = n - 1; i >= 0; i--)for (int j = i + 1; j < n; j++)a[i][n] ^= a[i][j] & a[j][n];return 0;
}

题目

以AtCoder Beginner Contest 366 G. XOR Neighbors 为例

将相邻点的限制列为一个方程作限制，

每个点非0，所以每个点占据二进制位中的一位，

钦定第i个点在第i位为1，解满足这n+1个限制条件的异或高斯消元方程

对于无穷解的情况，秩r<n，这里钦定所有自由元均为0，

第i行的主元并不一定在第i位，倒着遍历每一行，消去得到第i行的主元的解

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;const int N = 62;
int a[N][N],x[N];
int n,m,u,v;
ll b[N];
vector<int>e[N];// 异或高斯消元模板
int gauss(int n)//n*n矩阵，返回0表示有唯一解，r<n表示有无穷多组解(n-r个自由元)，-1表示无解
{int r, c;//分别表示行、列for (r = 0, c = 0; c < n; c++){//第一步：找出第c列中为1的任意一行int t = r;for (int i = r; i < n; i++)if (a[i][c]) { t = i; break; }if (!a[t][c]) continue;//如果所有方程的这一列都为0那么不进行操作//第二步：将这一行换至第一行(未确定方程的第一行)，即第r行for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);//第三步：将这一行之后的每一行的第c列的数变成0for (int i = r + 1; i < n; i++)if (a[i][c])for (int j = c; j <= n; j++)a[i][j] ^= a[r][j];r++;//处理完当前行，进入下一行}if (r < n){for (int i = r; i < n; i++)if (a[i][n]) return -1;  // 无穷多解，但这里还是令自由元都为0，解出一组解return n-r;}for (int i = n - 1; i >= 0; i--)for (int j = i + 1; j < n; j++)a[i][n] ^= a[i][j] & a[j][n];return 0;
}bool sol(){rep(u,0,n-1){memset(a,0,sizeof a);rep(i,0,n-1){for(auto &v:e[i]){a[i][v]=1;}}a[n][u]=a[n][n+1]=1;//钦定u为1int var=n+1;int t=gauss(var);if(t==-1)continue;//无解if(t==0 && a[n][var])continue;//无解if(t==0){rep(i,0,n-1){x[i]=a[i][var];}}else{//无穷解，这里不妨自由元全为0，倒着解出一组解//printf("t:%d\n",t);memset(x,0,sizeof x);for(int j=var-t-1;j>=0;--j){int tmp=a[j][var],tp,ok=1;for(int k=j;k<var;++k){if(!a[j][k])continue;if(ok){//找主元ok=0;tp=k;}else{ tmp^=x[k];}}x[tp]=tmp;}}rep(i,0,n-1){if(x[i]){b[i]|=(1ll<<u);}}}rep(i,0,n-1){if(!b[i])return 0;}return 1;
}int main(){sci(n);sci(m);rep(i,1,m){sci(u);sci(v);u--;v--;e[u].pb(v);e[v].pb(u);}if(!sol()){puts("No");}else{puts("Yes");rep(i,0,n-1){printf("%lld%c",b[i]," \n"[i==n-1]);}}return 0;
}

精简版

inline ll gauss() {rep(i, 1, n) {ll u = i;while(u <= L && !a[u][i]) ++u;if(u > L) return i;swap(a[i], a[u]);rep(j, 1, L) {if(i == j || !a[j][i]) continue;rep(k, 1, n + 1) a[j][k] ^= a[i][k];}}return 0;
}