怎么求矩阵对应的基呢？
对矩阵做初等行变换，化为上三角形 或 对角型， 主对角元素不为0的列即为该矩阵的一组基。
A =
这个矩阵对应的一个基 为
,
,
其实，将第二行的 -1 倍加到第一行上，化为
所以基也可以是，
，这个就对应的平面直角坐标系的正交的一组基。
（啰嗦一下，A矩阵其实对应的平面内的向量的变换， 伸缩变换和旋转变换。）
可求得，A矩阵的一个相似矩阵 B =
, （相似矩阵, 迹相等，行列式相等）
根据矩阵相似的含义， 存在可逆矩阵p, 使得
， 其实也是 BP = AP, 且 |P|
0
下面问题 ： 1，怎么求 可逆矩阵P ？
自己根据定义，设
, 求出
对该矩阵做初等行变换,化为上三角形或者对角型,主对角线元素不为零的列即为该矩阵的一组基.
转载于:https://www.cnblogs.com/oxspirt/p/10168921.html
注意：线性基的本质是解异或方程组
它与高斯消元的本质区别是：没有回代，于是可以在log情况下求出最大值
于是怎么搞？
Insert表示插入，原理是把每个数映射进数组，是原数集的异或集，可以理解用On的线性空间压制了一个On^2的东西。
那么查询最大值就是按位贪心。
从大到小，因为高位只是表示是否存在这一位，并不表示只有这一种。
和异或高斯消元的求可达性是本质如一的。
注意！！！！
由于常量数（1啊，233啊，999之类）是INT
所以要转long long
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=2e6+100; typedef int INT; #define int long long inline void read(int &x){ x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f; } struct Linear_basis{ int a[N]; Linear_basis(){ memset(a,0,sizeof(a)); } bool Insert(int x){ for(int i=60;i>=0;i--){ if(x&((int)1<<i)){ if(!a[i]){ a[i]=x; break; } x^=a[i]; } } return x>0; } int Query(){ int ret=0; for(int i=60;i>=0;i--){ if((ret^(a[i]))>ret) ret^=(a[i]); } return ret; } }A; INT main(){ int n; read(n); for(int i=1;i<=n;i++){ int x; read(x); A.Insert(x); } cout<<A.Query(); }转载于:https://www.cnblogs.com/Leo-JAM/p/10079269.html
3168: [Heoi2013]钙铁锌硒维生素
题意：给一个线性无关组A，再给一个B，要为A中每个向量在B中选一个可以代替的向量，替换后仍然线性无关。判断可行和求字典序最小的解
PoPoQQQ orz
显然是一个二分图匹配的模型
A是一个线性基，用它把B中每个向量表示出来，那么\(B_i\)可以替换\(A_j\)当且仅当表示\(B_i\)用到了\(A_j\)
可是A并不是每一位独立，怎么求表示啊？
A和B可以看成两个矩阵(横向量组)
\(C*A=B \rightarrow C=B*A^{-1}\)
\(C_{i,j}=1\)说明表示\(B_i\)用到了\(A_j\)，那么\(C^T\)就是这个二分图的邻接矩阵了求矩阵的逆
这里说一种方法，对A进行高斯约当消元，右面的常数列换成单位矩阵。校园后，左面变成了单位矩阵，右面就是\(A^{-1}\)
二分图匹配字典序最小的解
求任意一个完美匹配，然后从1到n贪心选择字典序最小的解，方法和hungary类似，但是要比较匹配点和当前点的字典序
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef unsigned long long ll; const int N=305, P=1e9+7; inline int read() { char c=getchar(); int x=0, f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f; } inline ll Pow(ll a, int b) { ll ans=1; for(; b; b>>=1, a=a*a%P) if(b&1) ans=ans*a%P; return ans; } inline void mod(int &x) {if(x<0) x+=P; else if(x>=P) x-=P;} int n, g[N][N]; char s[N]; struct Matrix { int a[N][N]; Matrix(){memset(a, 0, sizeof(a));} int* operator [](int x) {return a[x];} inline void im() {for(int i=1; i<=n; i++) a[i][i]=1;} void print() {for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) printf("%d%c",a[i][j],j==n?'\n':' ');} }a, b, c; Matrix inverse(Matrix a) { Matrix c; c.im(); for(int i=1; i<=n; i++) { int r; for(r=i; r<=n; r++) if(a[r][i]) break; // r != n+1 if(r!=i) for(int j=1; j<=n; j++) swap(a[i][j], a[r][j]), swap(c[i][j], c[r][j]); ll inv = Pow(a[i][i], P-2); for(int j=1; j<=n; j++) a[i][j] = a[i][j]*inv%P, c[i][j] = c[i][j]*inv%P; for(int k=1; k<=n; k++) if(k!=i) { ll t = a[k][i]%P; for(int j=1; j<=n; j++) mod(a[k][j] -= a[i][j]*t%P), mod(c[k][j] -= c[i][j]*t%P); } } return c; } Matrix operator *(Matrix a, Matrix b) { Matrix c; for(int i=1; i<=n; i++) for(int k=1; k<=n; k++) if(a[i][k]) for(int j=1; j<=n; j++) mod(c[i][j] += (ll)a[i][k]*b[k][j]%P); return c; } int vis[N], le[N]; bool dfs(int u) { for(int v=1; v<=n; v++) if(!vis[v] && g[u][v]) { vis[v]=1; if(!le[v] || dfs(le[v])) { le[v]=u; return true; } } return false; } bool dfs(int u, int now) { for(int v=1; v<=n; v++) if(!vis[v] && g[u][v]) { vis[v]=1; if(le[v]==now || (le[v]>now && dfs(le[v], now))) { le[v]=u; return true; } } return false; } int main() { freopen("in","r",stdin); //freopen("ferrous.in","r",stdin); //freopen("ferrous.out","w",stdout); n=read(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = read(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) b[i][j] = read(); c = b * inverse(a); //puts("c");c.print(); //Matrix t = a * inverse(a); puts("t"); t.print(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(c[i][j]) g[j][i]=1; for(int i=1; i<=n; i++) { memset(vis, 0, sizeof(vis)); if(!dfs(i)) {puts("NIE"); return 0;} } puts("TAK"); for(int i=1; i<=n; i++) { memset(vis, 0, sizeof(vis)); dfs(i, i); } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(le[j]==i) printf("%d\n",j); }
线性基是什么？
一个原序列能求出至少一组线性基
线性基是一个集合
第一，原序列中的任意一个数都可以通过线性基中的一些数异或得到
第二，线性基中的个数是一定的（取决于原序列，下面会讲）它不会重复
即线性基中的某些数异或的值不会存在线性基中，或者说线性基中的一些数异或起来不会等于0线性基又有什么作用呢？为什么要求线性基？
用于减少时间复杂度
线性基的长度大约为log（n）（n为原序列的长度）
原序列和它的线性基在异或操作这个层面上是等价的
所以用线性基来代替它的原序列来处理就可以了线性基怎么求？
d数组代表原序列的线性基，x代表原序列中的某个元素
d[i]表示x在二进制下的最高位的位置位i+1（i从0开始）
有人会问了
如果有2个数的x和y的最高位的位置都是i+1怎么办？
首先d[i]值能存一个值，那么d[i]先存x，那么可以把y变成x^y， 因为x^ (x^y)=y，再存y，如果这时的y的最高位和z的是最高位的位置一样，且z已经被存进去了怎么办？那把再把y变成 y^z，直到y能存进去为止
那如果把整个d数组都遍历完了都存不进去怎么办？
说明y不能存进去，也就是说如果把y存进去，线性基会出现一些数异或得到0的情况，就会重复，即这个y可以通过已有的线性基中的一些数异或得到
下面是代码void insert(ll x){ for(int i=62;i>=0;i--) if(x&(1ll<<i)) { if(d[i])x^=d[i]; else { d[i]=x; return; } } f=1;//标记有没有不能存进去的数 }下面是关于线性基的一些应用
求在一个序列中，取若干个数，使得它们的异或和最大ll getmax(){ ll ans=0; for(int i=62;i>=0;i--) if(ans^d[i]>ans)ans^=d[i]; return ans; }求最小
ll getmin(){ if(f)return 0; for(int i=0;i<=62;i++) if(d[i])return d[i]; }求第k小的值
从一个序列中取任意个元素进行异或，求能异或出的所有数字中第k小的那个
我们先来看一下
a1=1 0 1 0 0， a2=1 1 1 0 0
----b=1 1 1 1, -------b=1 1 1 1
a1异或b会得到比a1大的数，而a2异或b会得到比a2小的数
只要a的第4位（b的最高位的位置为4）为0那么a异或b的值一定大于a
那么我们需要重组一个线性基使他们变成这样
那么得到的d数组中的任意2个数异或都会变大
d[0]<d[1]<d[2]<d[3]<…
最小的数为d[0];
第二小的数为d[1];
第三小的数为d[0]^d[1];
第四小的数为d[2];
第五小的数为d[0]^d[2]
以此类推能得到如果k=10110；
那么第k小的数为d[1]^d[2] ^d[4];
代码void rebuild(){ for(int i=62;i>=1;i--) for(int j=i-1;j>=0;j--) if(d[i]&(1ll<<j))d[i]^=d[j]; for(int i=0;i<=62;i++) if(d[i])p[cnt++]=d[i]; } ll getkth(ll k){ if(f)--k; if(!k)return 0; if(k>=(1ll<<cnt))return -1; ll ans=0; for(int i=0;i<cnt;i++) if(k&(1ll<<i))ans^=p[i]; return ans; }#include<bits/stdc++.h> using namespace std; typedef long long ll; ll d[100],sum; int t; struct node{ ll n,m; }a[2000]; bool cmp(node x,node y) { return x.m>y.m; } bool insert(ll x) { for(int i=62;i>=0;i--) if(x&(1ll<<i)) { if(d[i])x^=d[i]; else{d[i]=x;return 1;} } return 0; } int main() { scanf("%d",&t); for(int i=0;i<t;i++)scanf("%lld%lld",&a[i].n,&a[i].m); sort(a,a+t,cmp); for(int i=0;i<t;i++)if(insert(a[i].n))sum+=a[i].m; cout<<sum<<endl; return 0; }#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=2008; ll d[200]; int n,m,cnt; string s; void insert(ll x) { for(int i=62;i>=0;i--) { if(x&(1ll<<i)) { if(d[i])x^=d[i]; else{d[i]=x;return;} } } } void rebuild() { for(int i=62;i>=1;i--) for(int j=i-1;j>=0;j--) if(d[i]&(1ll<<j))d[i]^=d[j]; for(int i=0;i<=62;i++) if(d[i])cnt++; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { cin>>s; ll a=0; for(int j=0;j<n;j++) { a<<=1; if(s[j]=='O')a++; } insert(a); } rebuild(); cout<<(1ll<<cnt)%mod<<endl; return 0; }nowcoder牛牛数数
用个二分求这个数是不是大于k，找到第一个大于k的位置
再减一下就能得到答案#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; ll d[100],p[100],k,a; int n,cnt; bool f=0; void insert(ll x){ for(int i=62;i>=0;i--) if(x&(1ll<<i)) { if(d[i])x^=d[i]; else{d[i]=x;return;} } f=1; } void rebuild(){ for(int i=62;i>=1;i--) for(int j=i-1;j>=0;j--) if(d[i]&(1ll<<j))d[i]^=d[j]; for(int i=0;i<=62;i++) if(d[i])p[cnt++]=d[i]; } ll getkth(ll k){ if(f)--k; if(!k)return 0; if(k>=(1ll<<cnt))return -1; ll ans=0; for(int i=0;i<cnt;i++) if(k&(1ll<<i))ans^=p[i]; return ans; } int main() { scanf("%d%lld",&n,&k); for(int i=1;i<=n;i++)scanf("%lld",&a),insert(a); rebuild(); ll l=1,r=(1ll<<cnt)+f-1; while(l<r) { ll m=l+r>>1; if(getkth(m)>k)r=m; else l=m+1; } cout<<(1ll<<cnt)-l+f<<endl;//由于线性基得不到0所以f用来表示0存不存在 return 0; }
