首页 > 其他分享 >高斯消元与线性基

高斯消元与线性基

时间:2022-11-30 22:34:45浏览次数:62  
标签:int 矩阵 异或 高斯消 线性 oplus 向量

高斯消元与线性基

Guass—约旦消元

消元算法

简介:这是求解线性方程组(也就是M个N元一次方程组)的方法

思想:我们可以把方程组看作一个系数矩阵

例如:

\[\left\{ \begin{aligned} 2x_1+x_2&-3x_3+x_4&=&2 \\ -x_1-6x_2&+2x_3-x_4&=&-9 \\ -x_1+6x_2&-2x_3+2x_4&=&12 \\ \end{aligned} \right. \]

可以写作系数矩阵:

\[\left[ \begin{matrix} 2 & 1 & -3 & 1 & 2\\ -1 & -6 & 2 & -1 & -9\\ -1 & 6 & -2 & 2 & 12\\ \end{matrix} \right] \]

其中最后一列是常数列

对这个矩阵作三类操作,以此求出方程组的解:

1.用一个非零的数乘某一行

2.把其中的一行的若干倍加在另一行上

3.交换两行位置

具体的,我们一次考虑第\(i\)列,为了将最后的矩阵变为一个对角矩阵(此时就是答案矩阵)

我们设当前已经使用了\(w\)个未知数进行消元,那么我们从第\(w+1\)行开始寻找第\(w+1\)个未知数的系数不为零的一行,将其交换至\(w+1\)行,然后对每一行(除了自己)与当前这个方程进行加减消元,这样我们就消去了除\(w+1\)行之外的所有第\(w+1\)个未知数

因为这个步骤,我们在从\(w+1\)行开始寻找的时候,第\(w+1\sim n\)(\(n\)为总行数)中前\(w\)个未知数的系数全是\(0\),且\(1\sim w\)行的未知数有系数的只有一个,也就是第\(i\)行的第\(i\)个未知数

算法见模板:

小部件厂

题目描述:

小部件工厂生产几种不同类型的小部件。

每个小部件都是精心制作而成。

制作小部件所需的时间取决于其类型:简单小部件仅需要 3 天,但最复杂的小部件可能需要多达 9 天。

工厂目前处于完全混乱的状态:最近,工厂被一位新主人收购,新主人解雇了几乎所有员工。

新员工对制作小部件毫无经验,没有人清楚制作每个不同类型的小部件分别需要多少天。

当客户订购小部件,工厂却无法告诉客户生产所需商品需要多少天时显得十分尴尬。

幸运的是,这里有记录记载了每个工人开始制作的日期,完成制作的日期以及制作的小部件型号。

但是问题是记录没有明确记载工人开始和完成工作的确切日期,只记录了该天是星期几。

尽管如此,这些信息也是有些帮助的:例如,如果一个人在星期二开始制作一个 41 型小部件,并在周五完成,那么我们就知道了制作一个 41 型小部件需要 4 天时间(因为最多不超过 9 天,所以不可能是 11 天或更多)。

您的任务是从这些记录中(如果可能)找出制作不同类型的小部件所需的天数。
这里是求解的关于模7的线性同余方程组

分析

这道题明摆着就是让我们求一个关于模7的线性同余方程组,有若干个未知数,我们采用高斯消元解决

#define mod %
int p=7;
using namespace std;
int a[305][305],n,m,ans[305],tot;
map<string ,int >w;
int get(int a,int b){
	return (b-a+8)%p;
} 
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int z=x;
	x=y,y=z-(a/b)*y;
	return d;
}
void init(){
	w["MON"]=1;
	w["TUE"]=2;
	w["WED"]=3;
	w["THU"]=4;
	w["FRI"]=5;
	w["SAT"]=6;
	w["SUN"]=7;
}
void Guass(){
	int w=0;
	for(int i=1;i<=m;i++){
		int o=0;
		for(int j=w+1;j<=n;j++){
			if(a[j][i]&&(!o||a[j][i]>a[o][i])){
				o=j;
			}
		}
		if(!o)continue;
		++w;
		for(int k=1;k<=m+1;k++)swap(a[w][k],a[o][k]);
		for(int j=1;j<=n;j++){
			if(j!=w&&a[j][i]){
				int x=a[j][i];
				for(int k=1;k<=m+1;k++)a[j][k]=(a[j][k]*a[w][i]-a[w][k]*x)%p;
			}//这里因为mod的缘故不能除,故我们可以构造lcm来加减
		}
	} 
	for(int i=w+1;i<=n;i++){
		a[i][m+1]%=p;
		if(a[i][m+1]){
			printf("Inconsistent data.\n");//无解
			return ;
		}
	}
	if(w<m){
		printf("Multiple solutions.\n");//多解(可确定的解(主元)比未知数数量少)
		return ;
	}
	for(int i=1;i<=m;i++){//求解线性同余方程:a[i][i]*x=a[i][m+1] mod 7; 
		int x,y,d;
		d=exgcd(a[i][i],7,x,y);
		x=x*a[i][m+1]/d;
		if(a[i][m+1]%d){//同余式无解 
			printf("Inconsistent data.\n"); 
			return ;
		} 
		ans[++tot]=((x-3)%p+p)%p+3;
	}
	for(int i=1;i<=tot;i++)printf("%d ",ans[i]);
	puts("");
	return ;
} 
int main(){
	init();
	while(~scanf("%d%d",&m,&n)&&m&&n){
		tot=0;
		memset(a,0,sizeof a);
		string x,y;
		int k;
		for(int i=1;i<=n;i++){
			cin>>k>>x>>y;
			a[i][m+1]=get(w[x],w[y]);
			for(int j=1;j<=k;j++){
				int q;
				scanf("%d",&q);
				a[i][q]++; 
				a[i][q]%=p;
			}
		}
		Guass();
	}
}

这里说明一下:

无解的情况:即化到最后出现\(0=d\)的情况,即所有未知数系数为0,但右边常数不为零

多解的情况:出现全0行,这种未知数我们称作自由元,其余叫主元

总结一下就是:在高斯消元完成后如果存在系数全0,常数不为零的行,则无解,若系数不全为0的行有\(N\)个,则说明主元有\(N\)个,方程有唯一解,如果系数不全为0的行有\(k\)个,则说明主元有\(k\)个,自由元有\(n-k\)个

线性空间与线性基

线性空间是一个关于以下两个运算封闭的向量集合(向量可理解为一个一维数组)

1.向量加法\(a+b\),其中\(a,b\)均为向量

2.标量乘法\(k\times a\),其中\(a\)是向量,\(k\)是常数(标量)

给定若干个向量\(a_1,a_2,a_3…a_k\),如果向量\(b\)能够被向量\(a_1,a_2,…a_k\)经过向量加法和标量乘法得出,则称向量b可以被向量\(a_1,a_2…a_k\)表出,显然,\(a_1,a_2,a_3…a_k\)能表示出的所有的向量构成一个线性空间,而\(a_1,a_2,a_3…a_k\)被称为这个线性空间的生成子集

任意选出线性空间中的若干个向量,若存在一个向量可以被其余向量表出,则称这些向量线性相关,否则称这些向量线性无关

线性空间的生成子集被称为这个线性空间的基底,简称基。基的另一种定义是线性空间的极大无关生成子集,一个线性空间的所有的基所包含的向量个数都相等(一个线性空间可能不止一个基),这个数被称之为线性空间的维数

例如平面直角坐标系就是一个二维线性空间,它的基就是单位向量集合\((0,1),(1,0)\)

对于一个\(n\)行\(m\)列的矩阵来说,我们可以把它的每一行看作一个长度为\(m\)的向量,称为行向量。矩阵的\(n\)个行向量能表出的所有向量组成一个线性空间,它的维数就是矩阵的行秩,类似的我们可以定义出矩阵的列秩,事实上,矩阵的行秩一定等于列秩,它们都是矩阵的秩。

把这个矩阵进行\(Guass\text{—约旦消元}\)(增广矩阵最后一列(即正常求方程组解的常数列)全看作0)得到一个简化阶梯型矩阵,显然这个矩阵的所有非0行向量线性无关,因为那三个操作就是做的标量乘法和向量加法。于是,简化阶梯型矩阵的所有非0行向量就是该线性空间的一个基,个数就是矩阵的秩

异或空间

类似于线性空间的定义,将向量加法和标量乘法换成异或运算就是异或空间,只不过异或空间表出来的就是一个数,而不是一个向量

至于求若干个数的异或空间的基,我们可以把这若干个数写为二进制形式的一个矩阵,对此进行消元即可。

不过求异或空间的基(简称线性基)我们有着其他的算法:

转载自:线性基总结

定义
基:

在线性代数中,基(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数。

线性基:

线性基是一种特殊的基,它通常会在异或运算中出现,它的意义是:通过原集合\(\mathbb{S}\)的某一个最小子集\(\mathbb{S_1}\)使得\(\mathbb{S_1}\)内元素相互异或得到的值域与原集合\(\mathbb{S}\)相互异或得到的值域相同。

也可以说是​在\(\bmod 2\)的意义下,有\(n\)个长度为\(m\)的向量,这\(n\)个向量的线性基为其所组成的线性空间\(V\)的基底。

1、原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
2、线性基里面的任意一些数异或起来都不能得到0。
3、线性基里面的数的个数唯一,并且在保持性质一的前提下,数的个数是最少的。

线性基的构造方法
构造线性基,我们考虑用增量法来构造线性基。假如现在要插入一个向量,从左向右不断消去1,直到出现了第一个无法消去的1,说明这个向量无法用现在的几组基底表示出来,所以将其插入线性基。

代码实现

ll d[65];
void addnum(ll x){
    for(int i=60;i>=0;i--)
    if((x>>i)&1){
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}

证明性质1
我们知道了线性基的构造方法后,其实就可以很容易想到如何证明性质1了,我们设原序列里面有一个数x,我们尝试用它来构造线性基,那么会有两种结果——1、不能成功插入线性基;2、成功插入线性基。

分类讨论一下
1、不能成功插入线性基
什么时候不能插入进去呢?
显然就是它在尝试插入时异或若干个数之后变成了0。
那么就有如下式子:
\(x\oplus d[a]\oplus d[b]\oplus d[c]...=0\)

根据上面的那个小性质,则有:
\(d[a]\oplus d[b]\oplus d[c]\oplus ...=x\)

所以,如果x不能成功插入线性基,一定是因为当前线性基里面的一些数异或起来可以等于x。

2、可以成功插入线性基
我们假设x插入到了线性基的第i个位置,显然,它在插入前可能异或若干个数,那么就有:
\(x\oplus d[a]\oplus d[b]\oplus d[c]\oplus …=d[i]\)

所以\(d[i]\oplus d[a]\oplus d[b]\oplus d[c]\oplus …=x\)

所以显然,x此时也可以由线性基里面的若干个数异或得到。

综上,性质一得证

证明性质2
由反证法:

假设线性基中存在\(d[a]\oplus d[b]\oplus d[c]=0\)
则\(d[a]\oplus d[b]=d[c]\)
因此\(d[c]\)根本无法插入线性基中,与假设矛盾。
所以性质二得证。

性质三证明略
推荐大佬博客:证明3

那么这玩意到底有啥用呢?

求异或最大值

ll getmax(){
    ll res=0;
    for(int i=60;i>=0;i--)
        if(res^d[i]>res)
            res^=d[i];
    return res;
}

求异或最小值

ll getmin(){
    ll res=0,cnt=0;
    for(int i=60;i>=0;i--)
        if(d[i])
            cnt++,res=d[i];
    if(cnt<n)return 0;
    return res;
}

求异或第k大值

例题

AC代码:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
ll d[65],d2[65],cnt;
void addnum(ll x){
    for(int i=60;i>=0;i--)
    if((x>>i)&1){
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
        if(x==0)break;
    }
}
void change(){
    for(int i=60;i>=0;i--){
        for(int j=i-1;j>=0;j--)
        if((d[i]>>j)&1){
            d[i]^=d[j];
        }
    }
    for(int i=0;i<=60;i++){
        if(d[i])d2[cnt++]=d[i];
    }
}
int main(){
    int _;
    scanf("%d",&_);
    for(int t=1;t<=_;t++){
        memset(d,0,sizeof d);
        cnt=0;
        printf("Case #%d:\n",t);
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            ll x;
            scanf("%lld",&x);
            addnum(x);
        }
        change();
        int q;
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            ll k;
            scanf("%lld",&k);
            if(n>cnt)k--;
            if(k>=(1ll<<cnt))printf("-1\n");
            else{
                ll res=0;
                for(int i=0;i<cnt;i++){
                    if(1&(k>>i))res^=d2[i];
                }
                printf("%lld\n",res);
            }
        }
    }
    return 0;
}

标签:int,矩阵,异或,高斯消,线性,oplus,向量
From: https://www.cnblogs.com/oierpyt/p/16939971.html

相关文章