高斯消元与线性基
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