4
10
2016
0

高斯消元求解xor问题 合集

WC2011 Xor 

对拍全正确,OJ上却4sWA了,只得了50 

 

d记录生成树数上s到每个点路径上xor 

a记录每个简单环的xor(树边xor^非树边 

cnt记录简单环(非树边)的个数  

 

LL d[N],a[N],cnt=0,ans;
bool v[N];
void dfs(int x)
{
	v[x]=true;
	R(i,x){
		int y=e[i].go;
		if(!v[y]){
			d[y]=d[x]^e[i].w;
			dfs(y);
		}
		else a[++cnt]=d[x]^d[y]^e[i].w;
	}
}

可用线性基做

 

int gauss_lb()
//高斯消元计算"线性基",即主元的个数--返回值 
{
	int k=1;//记录当前主元所在行 
	D(i,64,1){
		int t=0;//(记录当前列主元所在行的最大值) 
		F(j,k,cnt) if((a[j]>>i-1)&1) t=j;
		if(!t) continue;//如果该列不存在主元则找下一列 
		swap(a[k],a[t]);//(如果t==k则相当于不交换)
		F(j,k+1,cnt) if((a[j]>>i-1)&1) a[j]^=a[k];//消元成阶梯形矩阵
		k++;
	}
	return --k;//最后多算了一次,减去 
}
#include<bits/stdc++.h>
#define mec(a,x) memset(a,x,sizeof(a))
#define F(i,s,t) for(int i=(s);i<=(t);i++)
#define D(i,s,t) for(int i=(s);i>=(t);i--)
#define R(i,x) for(int i=head[x];i;i=e[i].nxt)
using namespace std;
const int inf=1<<30;
const int M=(int)1e5+10,N=50000+10;
typedef long long LL;
int n,m;
int head[N],tot=0;
struct edge{int fro,go,nxt;LL w;}e[M<<1];
void addedge(int x,int y,LL z)//无向图双向边 
{
	e[++tot]=(edge){x,y,head[x],z};head[x]=tot;
	e[++tot]=(edge){y,x,head[y],z};head[y]=tot;
}
/*****************************************/
LL d[N],a[N],cnt=0,ans;
bool v[N];
void dfs(int x)
{
	v[x]=true;
	R(i,x){
		int y=e[i].go;
		if(!v[y]){
			d[y]=d[x]^e[i].w;
			dfs(y);
		}
		else a[++cnt]=d[x]^d[y]^e[i].w;
	}
}
int gauss_lb()
{
	int k=1;
	D(i,64,1){
		int t=0;
		F(j,k,cnt) if((a[j]>>i-1)&1) t=j;
		if(!t) continue;
		swap(a[k],a[t]);
		F(j,k+1,cnt) if((a[j]>>i-1)&1) a[j]^=a[k];
		k++;
	}
	return --k;
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("xor.in", "r", stdin);
//	freopen("bzoj2115.txt", "w", stdout);
	#endif
	scanf("%d%d",&n,&m);
	F(i,1,m){
		int x,y;LL z;
		scanf("%d%d",&x,&y);
		scanf("%lld",&z);
		addedge(x,y,z);
	}
	dfs(1);
	ans=d[n];//d不参与消元 
	int num=gauss_lb();
	F(i,1,num) ans=max(ans,ans^a[i]);//该数(环)选or不选
	printf("%lld\n",ans); 
	return 0;
}

 


 

CQOI2013 新Nim游戏

在第一个回合中,第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿,但不可以全部拿走。

第二回合也一样,第二个游戏者也有这样一次机会。从第三个回合(又轮到第一个游戏者)开始,规则和Nim游戏一样。

问先手是否有必胜策略,如果可以获胜的话,要让第一回合拿的火柴总数尽量小。

50%:

关键:先手一定有必胜策略。(极端情况:拿走n-1堆)==>输出-1是坑nc的,我就nc了

对n<=10的数据,用二进制表示状态

直接暴力枚举每种第一轮A拿了过后的状态,再暴力枚举第一轮B拿了过后的状态,

判断合法后,对剩下的进行普通的Nim游戏,取所有合法状态拿走的最小总数即可

int n,tmp[N],a[N];
LL ans;
void work(int co)
{
	int tot=0;
	LL sum=0;//记录拿的总数
	for(int i=1;i<=n;i++)
		if(!(co&(1<<(i-1)))) tmp[++tot]=a[i];//剩余的状态
		else sum+=1ll*a[i];
	if(sum>ans) return;
	//枚举B拿的状态 1表示未拿,0表示拿
	for(int i=1;i<=(1<<tot)-1;i++){
		int t=0;
		for(int j=1;j<=tot;j++)
			if(i&(1<<(j-1))) t^=tmp[j];
		if(t==0) return;//不合法的情况!
	}
	ans=min(ans,sum);
	return;
}
/***main***/
if(n<=10){//用二进制数枚举A拿的状态:1表示拿了,0表示没拿
	ans=inf;
	for(int co=0;co<=(1<<n)-1;co++) work(co);
	printf("%lld\n",ans);
}

100%:

第一次拿完后,要使剩下的火柴中不存在异或和为0的子集,且让子集和最大 

求解极大线性无关组,即高斯消元求主元堆的火柴棒个数之和resans=sum-res 

 

b[]记录每列的主元:b[3]=a[2]表示matrix[3][2]为该列主元  

找到则break  

 

高斯消元(矩阵初等xor变换)后求线性基(主元) 

 附带线性基(主元)求和 

 注:不需要化为化简阶梯矩阵,即最后答案不一定有序, 

 消元前排一下序方便些 

LL gauss_lb()
{
	sort(a+1,a+n+1);
	D(i,n,1){
		int t=a[i];
		D(j,31,0) if(a[i]>>j&1){
			if(b[j]) a[i]^=b[j];//xor变换
			else{b[j]=a[i];break;} 
		}
		if(a[i]) res+=(LL)t;//该行没有被消为0==>存在主元 
	}
	return res;
}

 


CQOI2014 和谐矩阵matrix 

 

我们称一个由01组成的矩阵是和谐的,当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本 

身,及他上下左右的4个元素(如果存在)。 

给定矩阵的行数和列数,请计算并输出一个和谐的矩阵。注意:所有元素为0的矩阵是不允许的。 

题解(%regina8023 

高斯消元解异或方程组(具体做法见【POJ 1222】)。

有两种做法: 
①速度较慢的方法: 

对于矩阵中的每一个元素都可以列出一个方程,m∗n个未知数,m∗n个方程(f[i][j]表示第i个对第j个有影响): 

a[k]+f[1][k]∗a[1]+f[2][k]∗a[2]+...f[tot][k]∗a[tot]=0(mod2) 


 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[2000][2000],ans[2000],d[10][5],id[50][50],n,m;
void Gauss(int n,int m)
{
    for (int i=1;i<=n;i++)
    {
        int j;
        for (j=i;j<=m&&!a[j][i];j++);
        if (j>n) continue;
        if (j!=i)
            for (int k=i;k<=m;k++)
                swap(a[i][k],a[j][k]);
        for (int j=i+1;j<=n;j++)
            if (a[j][i])
                for (int k=i;k<=m;k++)
                    a[j][k]^=a[i][k];
    }
    for (int i=n;i;i--)
    {
        if (!a[i][i])
        {
            ans[i]=1;
            continue;
        }
        for (int j=i+1;j<=n;j++)
            a[i][m]^=(ans[j]*a[i][j]);
        ans[i]=a[i][m];
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    d[0][1]=d[0][2]=0;
    d[1][1]=d[2][1]=0,d[1][2]=1,d[2][2]=-1;
    d[3][2]=d[4][2]=0,d[3][1]=1,d[4][1]=-1;
    int cnt=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            id[i][j]=++cnt;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=0;k<=4;k++)
            {
                int p=id[i+d[k][1]][j+d[k][2]];
                if (p) a[id[i][j]][p]=1;
            }
    Gauss(cnt,cnt+1);
    cnt=0;
    for (int i=1;i<=n;i++)
    {
        printf("%d",ans[++cnt]);
        for (int j=2;j<=m;j++)
            printf(" %d",ans[++cnt]);
        printf("\n");
    }
    return 0;
}

 

②速度快的办法:

如果第一行的数知道了,我们就可以推出其他行的数。

那么如何判断第一行的数的一种填法是否合法呢?很简单,我们递推出m+1行的数,当且仅当这一行都是0时满足题意。

那么,我们就有了一种想法。

直接把m+1行的每个数用x[1..n]表示出来,这一定是个系数只为0/1的式子。然后让这个异或值=0,就可以解异或方程组了。

系数怎么推呢?

for1(i,n)b[1][i]=(ll)1<<i-1;
    for2(i,2,m+1)
     for1(j,n)
      b[i][j]=b[i-1][j]^b[i-1][j-1]^b[i-1][j+1]^b[i-2][j];

然后解方程就可以了。


 

代码(贴上别人跑得快的) 

 

#define rep(i,x,y) for(int i=x;i<=y;i++)
#define drp(i,x,y) for(int i=x;i>=y;i--)

typedef long long LL;

const int N=52;

int n,m;
LL a[N]={0},b[N][N]={0};
bool c[N][N]={0};

void  Gauss() {
	rep(i,1,m) {
		int j=i;
		while (j<=m&&!(a[j]>>i-1&1)) j++;
		if (j>m) continue;
		swap(a[i],a[j]);
		rep(k,i+1,m) if (a[k]>>i-1&1)
			a[k]^=a[i];
	}
	drp(i,m,1) {
		c[1][i]=a[i]>>m&1;
		if (!(a[i]>>i-1&1)) {c[1][i]=1;continue;}
		rep(j,i+1,m) if (a[i]>>j-1&1)
			c[1][i]^=c[1][j];
	}
}

int main() {
//	freopen("test.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,1,m) b[1][i]=(LL)1<<i-1;
	rep(i,2,n+1) rep(j,1,m)
	b[i][j]=b[i-1][j]^b[i-2][j]^b[i-1][j-1]^b[i-1][j+1];
	rep(i,1,m) a[i]=b[n+1][i];
	Gauss();
	rep(i,2,n) rep(j,1,m)
	c[i][j]=c[i-1][j]^c[i-2][j]^c[i-1][j-1]^c[i-1][j+1];
	rep(i,1,n) {rep(j,1,m) printf("%d ",c[i][j]);printf("\n");}
  return 0;
}

 

Category: 数学相关 | Tags: 矩阵 高斯消元 博弈论 | Read Count: 564

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com