## 1. 爪形行列式 1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&1& \cdots &1\\ 1&{{x_2}}& \cdots &0\\ \vdots & \vdots & \ddots &0\\ 1&0&0&{{x_n}} \end{array}} \right|$ ## 2. 两三角型行列式 1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&b& \cdots &b\\ b&{{x_2}}& \cdots &b\\ \vdots & \vdots & \ddots &b\\ b&b&b&{{x_n}} \end{array}} \right|$ 2. 求${D_n} = \left| {\begin{array}{*{20}{c}} {{x_1}}&b&b& \cdots &b\\ a&{{x_2}}&b& \cdots &b\\ a&a&{{x_3}}& \cdots &b\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&a&a& \cdots &{{x_n}} \end{array}} \right|$ 3. 求${D_n} = \left| {\begin{array}{*{20}{c}} d&b&b& \cdots &b\\ c&x&a& \cdots &a\\ c&a&x& \cdots &a\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c&a&a& \cdots &x \end{array}} \right|$ ## 3. 两条线型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1}}&{{b_1}}&0& \cdots &0\\ 0&{{a_2}}&{{b_2}}& \cdots &0\\ 0&0&{{a_3}}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{b_n}}&0&0& \cdots &{{a_n}} \end{array}} \right|$ ## 4. 范德蒙德型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n \end{array}} \right|$ ## 5. Hessenberg型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&2&3& \cdots &n\\ 1&{ - 1}&0& \cdots &0\\ 0&2&{ - 2}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &{1 - n} \end{array}} \right|$ ## 6. 三对角型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} a&b&0& \cdots &0\\ c&a&b& \cdots &0\\ 0&c&a& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &a \end{array}} \right|$ ## 7. 各行元素和相等型行列式 * 求${D_n} = \left| {\begin{array}{*{20}{c}} {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\ {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\ {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}} \end{array}} \right|$ ## 8. 相邻两行对应元素相差K倍型行列式 1. 求${D_n} = \left| {\begin{array}{*{20}{c}} 0&1&2& \cdots &{n - 1}\\ 1&0&1& \cdots &{n - 2}\\ 2&1&0& \cdots &{n - 3}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n - 1}&{n - 2}&1& \cdots &0 \end{array}} \right|$ 2. 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\ {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\ {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&{{a^2}}&{{a^3}}& \cdots &1 \end{array}} \right|$
Category: 线性基
【BZOJ 3811】玛里苟斯
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ:https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ:http://yyy.is-programmer.com/posts/200623.html
解题报告
这题这么神,我们来分情况讨论:
1. $k = 1$
这就是一般的期望题。因为期望的线性,所以我们在二进制位下每一位分开考虑:
如果这一位上每一个数都是$0$,那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$
证明的话,可以设$f_{1,0/1}$为考虑到第i个数,异或起来为0/1
的概率
写出$DP$式子可以很轻松地发现这俩总是对半分,Q.E.D
于是我们直接把所有数$or$起来,然后除二输出即可
时间复杂度:$O(n)$
2. $k = 2$
这不是一般的期望题了,不是线性的,不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$
因为$b_i$与$b_j$是线性的,所以我们就可以枚举$i,j$然后直接加起来了!
根据$k = 1$时得到的结论,不难发现:
如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立,那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过,那么概率为$0$
于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度:$O(62n + 62^2)$
3. $k \ge 3$
我们先来看一个结论:若$E(x^k) < 2^{63}$,初始集合中的每个数小于$2^{22}$
证明的话,sengxian教我的:
不妨用反证法,考虑答案为:$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$,有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了,又因为答案小于$2^{63}$,矛盾,故不可能,Q.E.D
所以我们可以求出这些数的线性基,然后暴力枚举线性基的子集
根据$k = 1$时的人生经验,我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举,然后暴力算贡献就可以了
时间复杂度:$O(21n + 2^{21})$
【BZOJ 4644】经典傻逼题
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4644
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5734792.html
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/53997223
解题报告
首先,如果我们把边权异或到点上
原问题就可以转化为:选一些点,使NIM和最大
于是就是线性基的锅了,时间复杂度:$ \frac{{nm{L^2}}}{{{\rm{64}}}}$
然后我们发现这么做会T
于是对时间进行分治
这样的话,复杂度优化到:$ \frac{{m\log m{L^2}}}{{{\rm{64}}}}$
然后Claris还说可以用Method of Four Russians
这样话,复杂度就变成了:$ \frac{{m\log m{L^2}}}{{{\rm{64logL}}}}$
【POJ 1903】[NEERC2003] Jurassic Remains
题目传送门:http://poj.org/problem?id=1903
中文题面:《算法竞赛·入门经典·训练指南》P57
对于每一个字符串,不难将其转化为26维的0/1向量
于是求一个线性基就可以辣!
当然不会线性基该怎么搞?
白书上面给了一个很常用、实用的方法:
将向量分成两组,组内暴力
然后组间使用map来支持查询即可
【算法笔记】再再看线性基
这一次是以专题的形式
主要以这份题单作为主线:http://www.cnblogs.com/joyouth/p/5645682.html
感觉对于线性基已经理解透了?(大雾)
不过还是不会拟阵…
【Codeforces 662A】Gambling Nim
题目传送门:http://codeforces.com/problemset/problem/662/A
官方题解:http://codeforces.com/blog/entry/44408
说人话就是亦或和为0的概率是多少
考虑把ai全部亦或起来为sum的话
那就是求{ai^bi}有多少个子集亦或和为sum
这样的话,岂不就是线性基的拿手好戏了?
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 500000+9; const int SGZ = 61+9; int n,cnt; LL a[N],b[N],bas[SGZ],sum; inline LL read(){ char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline bool insert(LL w) { for (int i=61;~i;i--) if (w&(1LL<<i)) { if (bas[i]) { w ^= bas[i]; } else { bas[i] = w; return true; } } return false; } inline LL pow(LL w, int t) { LL ret = 1; while (t) { if (t & 1) ret *= w; w *= w; t >>= 1; } return ret; } int main(){ n = read(); for (int i=1;i<=n;i++) { a[i] = read(); b[i] = read(); sum ^= a[i]; cnt += insert(a[i] ^ b[i]); } if (!cnt && !sum) { puts("0/1"); } else if (insert(sum)) { puts("1/1"); } else { printf("%I64d/%I64d\n",pow(2LL,cnt)-1,pow(2LL,cnt)); } return 0; }
【BZOJ 2844】albus就是要第一个出场
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2844
数据生成器:http://paste.ubuntu.com/23312434/
话说这个题啊!还是挺有意思哒!
有一个结论:如果相同的数要计入答案的话,那每种答案出现了2^(n-线性基的数量)
证明:既然都为0了,那么取不取都不影响答案,于是可以随便搞一搞
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 10086; const int N = 100000+9; const int SGZ = 30+9; int n,m,arr[N],bas[SGZ],cnt,vout; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline bool insert(int w) { for (int i=30;~i;i--) if (w&(1<<i)) { if (bas[i]) { w ^= bas[i]; } else { bas[i] = w; return true; } } return false; } inline int pow(int w , int t) { int ret = 1; while (t) { if (t&1) ret = (LL)ret * w % MOD; w = (LL)w * w % MOD; t >>= 1; } return ret; } int main(){ n = read(); for (int i=1;i<=n;i++) { arr[i] = read(); cnt += insert(arr[i]); } m = read(); for (int i=30,tmp=pow(2,n-cnt);~i;i--) if (bas[i]) { cnt--; if (m&(1<<i)) { vout += tmp * (1LL<<cnt) % MOD; vout %= MOD; } } printf("%d\n",(vout+1)%MOD); return 0; }
【HDU 3949】XOR
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3949
这个题ihopenot都说是水题了,那我也扔一份代码就跑吧!
想看题解的戳这里:http://acm.hdu.edu.cn/showproblem.php?pid=3949
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 10000+9; int n,bas[70],cnt,m; LL arr[N],l,r,STA,tag; inline void insert(LL &w, int num) { for (int i=61;~i;i--) if (w & (1LL<<i)) { if (bas[i]) { w ^= arr[bas[i]]; } else { bas[i] = num; break; } } if (!w) tag = 1; } inline LL cal(LL w) { LL ret = 0; for (int i=0,cur=0;i<cnt;i++) { while (!bas[cur]) cur++; if (w&(1LL<<i)) ret ^= arr[bas[cur]]; cur++; } return ret; } inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ for (int T=read(),tot=1;T;T--,tot++) { printf("Case #%d:\n",tot); memset(bas,0,sizeof(bas)); memset(arr,0,sizeof(arr)); cnt = tag = 0; n = read(); for (int i=1;i<=n;i++) { cin>>arr[i]; insert(arr[i],i); } for (int i=0;i<=61;i++) if (bas[i]) { ++cnt; for (int j=i+1;j<=61;j++) if (bas[j]) { if (arr[bas[j]] & (1LL<<i)) { arr[bas[j]] ^= arr[bas[i]]; } } } m = read(); STA = (1LL<<cnt) - 1; for (int i=1;i<=m;i++) { LL tmp; scanf("%I64d",&tmp); tmp -= tag; if (STA < tmp) puts("-1"); else printf("%I64d\n",cal(tmp)); } } return 0; }
【BZOJ 3569】DZY Loves Chinese II
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器:http://paste.ubuntu.com/23227745/
这个题,是我到目前为止,做过的最妙的一道题
没有之一
给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况:删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样,判一下是否线性无关即可
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; const int M = 1000000+9; const int MOD = 9999971; const int SGZ = 40; int head[N],nxt[M],to[M],n,m,q,val[M]; int vis[N],c[SGZ],cnt,bas[SGZ],sym[N]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void Add_Edge(int u, int v) { static int T = 1; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } void DFS1(int w, int f) { vis[w] = 1; for (int i=head[w];i;i=nxt[i]) if (to[i] != f) { if (vis[to[i]]) { int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W; sym[w] ^= W; sym[to[i]] ^= W; } else DFS1(to[i],w); } } void DFS2(int w, int f) { for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i]) DFS2(to[i], w), val[i] ^= sym[to[i]], val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]]; } inline bool update(int w) { for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) { if (!bas[i]) {bas[i] = tmp; return false;} else {tmp ^= bas[i]; if (!tmp) return true;} } return val[w]?false:true; } int main(){ srand(9999971); n = read(); m = read(); for (int i=1;i<=m;i++) Add_Edge(read(),read()); DFS1(1,1); DFS2(1,1); for (int q=read(),k,tag;q;q--) { k = read(); tag = 1; memset(bas,0,sizeof(bas)); for (int i=1;i<=k;i++) c[i] = read()^cnt; for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0; if (tag) puts("Connected"), cnt++; } return 0; }
【BZOJ 4004】[JLOI2015] 装备购买
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4004
数据生成器:http://paste.ubuntu.com/23209631/
这个题目,看一眼,就是要求一组花费最小的线性基
第一次写,写的整数高斯消元,发现爆了long long
第二次改成double,发现精度不够
第三次,搞成整数高斯消元+MOD,遂过之
想一想,如果不用线性基,只是求一组线性基的话,MOD确实没影响
另外网上用double写的标程全部被叉掉了,不要问我是怎么知道的 qwq
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 500+9; const int MOD = 1000000007; int n,m,f[N][N],bas[N],cost[N],num[N],cnt,vout; inline int read(){char c=getchar(); int ret=0,f=1;while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret*f;} inline bool cmp(const int a, const int b) {return cost[a] < cost[b];} inline void update(int w) { for (int i=1;i<=m;i++) if (f[w][i]) { if (!bas[i]) {bas[i] = w, cnt++, vout += cost[w]; break;} else { int t2 = f[bas[i]][i], t1 = f[w][i]; for (int j=1;j<=m;j++) f[w][j] = ((LL)f[w][j]*t2 - (LL)f[bas[i]][j]*t1) % MOD; } } } int main(){ n = read(); m = read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j] = read(); for (int i=1;i<=n;i++) cost[i] = read(), num[i] = i; sort(num+1,num+1+n,cmp); for (int i=1;i<=n;i++) update(num[i]); printf("%d %d\n",cnt,vout); return 0; }
【BZOJ 3105】[cqoi2013] 新Nim游戏
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3105
这个题目,考虑两个回合之后。
假如对手能够在在第二个回合搞出一个Nim和为0的东西,那我们岂不是输了?
所以我们不能给对手搞出Nim和为0的机会,而Nim和为Xor,不存在子集Nim和为0是线性无关
而我们又要子集最大(损失最小),所以我们要求的是一个极大线性无关子集
然后我们发现,这货不是线性基吗?
于是水之
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int bas[32],arr[109]; inline bool update(int w) { for (int i=0;i<=31;i++) if (w & 1<<i) if (bas[i]) w ^= bas[i]; else {bas[i] = w; return 1;} return 0; } int main(){ int k = read(); LL vout = 0; for (int i=1;i<=k;i++) arr[i] = read(), vout += arr[i]; sort(arr+1,arr+1+k); for (int i=k;i;i--) vout -= update(arr[i])*arr[i]; printf("%lld\n",vout); return 0; }
【BZOJ 4568】[Scoi2016] 幸运数字
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器:http://paste.ubuntu.com/23202923/
《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看,结果最开始写的是链剖,T到死 ←是男人就去ZGS的OJ上测,单点时限
后来重新写了LCA的版本,又T到死
于是暴力优化常数,最终5.9s勉强卡过
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 20000+9; int n,q,head[N],nxt[N*2],to[N*2]; LL arr[N]; inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;} inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;} inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } namespace LCA{ int fa[N][16],dep[N]; LL f[N][16][61],POW[61]; void DFS(int w, int f) { fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1; for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w); } inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;} inline void merge(LL *a, LL *b) { for (int i=60;~i;i--) if (b[i]) { LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) { if (!a[j]) {a[j] = w; break;} else w ^= a[j]; } } } inline void init() { for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;} for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]); for (int i=1;i<=n;i++) for (int j=2;j<=15;j++) fa[i][j] = fa[fa[i][j-1]][j-1], memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])), merge(f[i][j],f[fa[i][j-1]][j-1]); } inline LL query(int x, int y) { static LL bas[61]; memset(bas,0,sizeof(bas)); if (dep[x] < dep[y]) swap(x,y); for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y]) merge(bas,f[x][i]), x = fa[fa[x][i]][1]; if (x == y) merge(bas,f[x][0]); else { for (int i=15;~i;i--) if (fa[x][i] != fa[y][i]) merge(bas,f[x][i]), merge(bas,f[y][i]), x = fa[fa[x][i]][1], y = fa[fa[y][i]][1]; merge(bas,f[x][0]); } LL ret = 0; for (int i=0;i<=60;i++) if (bas[i]) for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i]; for (int i=0;i<=60;i++) ret ^= bas[i]; return ret; } }; int main(){ n = read(); q = read(); for (int i=1;i<=n;i++) arr[i] = readL(); for (int i=1;i<n;i++) Add_Edge(read(),read()); LCA::DFS(); LCA::init(); for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read())); return 0; }
另外,%Claris,直接上点分治:http://www.cnblogs.com/clrs97/p/5451814.html
【BZOJ 4269】再见Xor
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4269
离线版题目:http://paste.ubuntu.com/18971803/
这个题目,拿到以后,一脸懵逼啊QAQ,想拿BFS乱搞一搞,估计会T,结果还是可耻地看了题解
高斯消元求线性基QAQ,又没有学过QAQ,I well vegtable are (T_T)
其实也不难,每一个数的二进制看成方程组,然后上高斯消元。
求出线性基之后,全部^起来就是最大值,找一个最小的^一下就是次小值
#include<iostream> #include<cstdio> using namespace std; const int MAXN = 100000+9; int n,arr[MAXN],cnt; inline void Gauss(){ for (int k=31;k;k--){ int w = 1<<(k-1), pos; for (pos=cnt+1;pos<=n;pos++) if (arr[pos]&w) break; if (pos==n+1) continue; else { swap(arr[++cnt], arr[pos]); for (int i=1;i<=n;i++) if (i!=cnt && (arr[i]&w)) arr[i] ^= arr[cnt]; } } } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&arr[i]); Gauss(); int vout = 0; for (int i=1;i<=cnt;i++) vout ^= arr[i]; printf("%d ",vout); printf("%d\n",vout ^= arr[cnt]); return 0; }
好像还有一种方法,写法跟在线求解亦或方程组很像。
但感觉不如直接高斯消元优雅,且时间复杂度相同,所以就不贴代码啦!