登录
← 返回首页 | 代码片段 › 7 数论与数学 › 7.5 线性代数与高斯消元 › 线性代数与高斯消元 / 搜索
JSON MD

7.5 线性代数与高斯消元

高斯消元 Gauss
19 行
CPP JSON
【高斯消元法——解线性方程组(实系数)】 ▪ Gauss(a, n) — 对 n×(n+1) 的增广矩阵 a 做高斯消元: ① 列主元选取:每列找绝对值最大的行 r 作为主元行,提高数值稳定性 ② 消元:用第 i 行消去下方所有行第 i 列(a[j][k] -= t*a[i][k]) ③ 回代:从第 n 行向上,依次解出每个未知数 时间复杂度 O(N³)。含 eps 判零处理。适用于 n 元线性方程组、矩阵求逆、行列式计算。
C++ 19 行 CPP
bool Gauss(Matrix a, int n) {
    for(int i=1; i<=n; i++) {
        int r=i;
        for(int j=i+1; j<=n; j++) 
            if(abs(a[j][i]) > abs(a[r][i])) r=j;
        if(abs(a[r][i])<eps) return false;
        if(r!=i) for(int j=1; j<=n+1; j++) swap(a[r][j], a[i][j]);
        
        for(int j=i+1; j<=n; j++) {
            double t = a[j][i]/a[i][i];
            for(int k=i; k<=n+1; k++) a[j][k] -= t*a[i][k];
        }
    }
    for(int i=n; i>=1; i--) {
        for(int j=n; j>i; j--) a[i][n+1] -= a[i][j]*a[j][n+1];
        a[i][n+1] /= a[i][i];
    }
    return true;
}
高斯消元-解加法方程组 gauss-add
19 行
CPP JSON
【高斯消元——解异或(加法)方程组(GF(2) 域)】 ▪ Gauss(a, n) — 对 n×(n+1) 的增广矩阵在 GF(2) 域上做高斯消元: ① 列主元选取(找第 i 列绝对值最大的行) ② 消元(前向消去下方行) ③ 回代(从下往上解出各变量) 与 ID=11 的 Gauss 算法结构相同,但使用按位异或(^)替代加减法,在 GF(2) 域上操作。 时间复杂度 O(N³)。适用于解 XOR 方程组、开关灯问题、线性基构建等。
C++ 19 行 CPP
bool Gauss(Matrix a, int n) {
	for(int i=1; i<=n; i++) {
		int r=i;
		for(int j=i+1; j<=n; j++) 
			if(abs(a[j][i]) > abs(a[r][i])) r=j;
		if(abs(a[r][i])<eps) return false;
		if(r!=i) for(int j=1; j<=n+1; j++) swap(a[r][j], a[i][j]);
		
		for(int j=i+1; j<=n; j++) {
			double t = a[j][i]/a[i][i];
			for(int k=i; k<=n+1; k++) a[j][k] -= t*a[i][k];
		}
	}
	for(int i=n; i>=1; i--) {
		for(int j=n; j>i; j--) a[i][n+1] -= a[i][j]*a[j][n+1];
		a[i][n+1] /= a[i][i];
	}
	return true;
}
前缀线性基 Ivan and Burgers
40 行
CPP JSON
【前缀线性基(Ivan and Burgers)】 线性代数模板。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re x,Re id) — 插入元素 int ask(Re L) — 核心算法函数 核心结构体:JI 关键配置: N=5e5+3,logN=20,inf=2e9 说明:freopen("456.txt","r",stdin);
C++ 39 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,logN=20,inf=2e9;
int n,x,y,T;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct JI{
	int p[logN+1],ip[logN+1];JI(){memset(p,0,sizeof(p));}
	inline void insert(Re x,Re id){
		for(Re i=logN;i>=0;--i)
			if((x>>i)&1){
				if(!p[i]){p[i]=x,ip[i]=id;break;}
				if(ip[i]<id)swap(p[i],x),swap(ip[i],id);
				x^=p[i];
			}
	}
	inline int ask(Re L){
		Re ans=0;
		for(Re i=logN;i>=0;--i)if(ip[i]>=L)ans=max(ans,ans^p[i]);
		return ans;
	}
}A[N],S[N];
int main(){
//    freopen("456.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1],S[i].insert(x,i);
    in(T);
    while(T--)in(x),in(y),printf("%d\n",S[y].ask(x));
}
矩阵快速幂 结构体
48 行
CPP JSON
【矩阵快速幂(结构体)】 矩阵运算模板(乘法、快速幂、求逆)。 核心函数: void in(Re &x) — 核心算法函数 void read(无参数) — 核心算法函数 void print(无参数) — 核心算法函数 Matrix mi(Matrix x,Re k) — 核心算法函数 核心结构体:Matrix 关键配置: N=103,P=1e9+7
C++ 47 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=103,P=1e9+7;
LL n,K;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Matrix{
	LL a[N][N];
	Matrix(){memset(a,0,sizeof(a));}
	inline void read(){
		for(Re i=1;i<=n;++i)
    		for(Re j=1;j<=n;++j)	
    			in(a[i][j]);
	}
	inline void print(){
		for(Re i=1;i<=n;puts(""),++i)
    		for(Re j=1;j<=n;++j)	
    			printf("%lld ",a[i][j]);
	}
	inline Matrix operator*(const Matrix &O)const{
		Matrix ans;
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=n;++j)
				for(Re k=1;k<=n;++k)
					(ans.a[i][j]+=a[i][k]*O.a[k][j]%P)%=P;
		return ans;
	}
	inline Matrix operator*=(Matrix &O){return *this=*this*O;}
}A;
inline Matrix mi(Matrix x,Re k){
	if(!k)return x;--k;
	Matrix s=x;
	while(k){
		if(k&1)s*=x;
		x*=x,k>>=1;
	}
	return s;
}
int main(){
	in(n),in(K),A.read(),mi(A,K).print();
}
线性基 insert
28 行
CPP JSON
【线性基】 线性代数模板。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re x) — 插入元素 关键配置: N=55 说明:freopen("123.txt","r",stdin);
C++ 27 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const int N=55;
LL n,x,ans,p[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void insert(Re x){
	for(Re i=50;i>=0;--i)
		if((x>>i)&1){
			if(!p[i]){p[i]=x;break;}
			x^=p[i];
		}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)in(x),insert(x);
	for(Re i=50;i>=0;--i)ans=max(ans,ans^p[i]);
	printf("%lld\n",ans);
}
线性基合并 幸运数字
62 行
CPP JSON
【线性基合并(幸运数字)】 线性代数模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void insert(Re x) — 插入元素 void merge(JI O) — 合并操作 LL ask(无参数) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 JI ask(Re x,Re y) — 核心算法函数 核心结构体:QAQ, JI, LCA 说明:freopen("lucky.in","r",stdin);;freopen("lucky.out","w",stdout);
C++ 61 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register LL
using namespace std;
const LL N=2e4+3,M=2e5+3,inf=2e18,logN=14;
LL n,m,o,x,y,T,A[N],head[N];
struct QAQ{LL to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct JI{
    LL p[61];JI(){memset(p,0,sizeof(p));}
    inline void insert(Re x){
        for(Re i=60;i>=0;--i)
            if((x>>i)&1){
                if(!p[i]){p[i]=x;break;}
                x^=p[i];
            }
    }
    inline void merge(JI O){
        for(Re i=60;i>=0;--i)if(O.p[i])insert(O.p[i]);
    }
    inline LL ask(){
        Re ans=0;
        for(Re i=60;i>=0;--i)ans=max(ans,ans^p[i]);
        return ans;
    }
};
struct LCA{
    LL deep[N],fa[N][15],ant[N][15];JI dp[N][15];
    inline void dfs(Re x,Re fa){
        deep[x]=deep[ant[x][0]=fa]+1,dp[x][0].insert(A[fa]);
        for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1],dp[x][j]=dp[x][j-1],dp[x][j].merge(dp[ant[x][j-1]][j-1]);
        for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
    }
    inline JI ask(Re x,Re y){
        JI Ans;Ans.insert(A[x]),Ans.insert(A[y]);
        if(deep[x]<deep[y])swap(x,y);
        for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])Ans.merge(dp[x][i]),x=ant[x][i];
        if(x==y)return Ans;
        for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])Ans.merge(dp[x][i]),Ans.merge(dp[y][i]),x=ant[x][i],y=ant[y][i];
        Ans.merge(dp[x][0]);
        return Ans;
    }
}T1;
int main(){
//    freopen("lucky.in","r",stdin);
//    freopen("lucky.out","w",stdout);
    in(n),in(T),m=n-1;
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    T1.dfs(1,0);
    while(T--)in(x),in(y),printf("%lld\n",T1.ask(x,y).ask());
}
高斯消元 高斯约旦消元
39 行
CPP JSON
【高斯消元(高斯约旦消元)】 高斯消元法模板,求解线性方程组、矩阵求逆或行列式计算。 核心函数: int dcmp(Re a) — 核心算法函数 LD Abs(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 关键配置: N=103 说明:freopen("123.txt","r",stdin);
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=103;
int n;LD eps=1e-8,a[N][N];
inline int dcmp(Re a){return a<-eps?-1:(a>eps?1:0);}
inline LD Abs(LD a){return dcmp(a)*a;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)	
		for(Re j=1;j<=n+1;++j)
			scanf("%lf",&a[i][j]);
	for(Re j=1;j<=n;++j){
		Re w=j;
		for(Re i=j+1;i<=n;++i)
			if(dcmp(Abs(a[i][j])-Abs(a[w][j]))>0)w=i;
		for(Re k=1;k<=n+1;++k)swap(a[j][k],a[w][k]);
		if(!dcmp(a[j][j]))return !puts("No Solution");
		for(Re i=1;i<=n;++i)
			if(i!=j){
				LD tmp=a[i][j]/a[j][j];
				for(Re k=j;k<=n+1;++k)a[i][k]-=a[j][k]*tmp;
			}
	}
	for(Re i=1;i<=n;++i)printf("%.2lf\n",a[i][n+1]/a[i][i]);
}
已复制