【线性基总结】
線性積基于線性代數(shù)中的無關(guān)向量組
回顧線性代數(shù)中的無關(guān)向量組的無關(guān)性,若兩個向量線性相關(guān)，肯定可以相互表示,
ax1+bx2+cx3=0有不全為0的數(shù)表示，則說明向量組x1 x2 x3是線性相關(guān)的
若一個矩陣可逆,還有他的秩不為0,構(gòu)成這個矩陣的向量組線性無關(guān)
1.線性基的異或集合中不存在0。
2.線性基的異或集合中每個元素的異或方案唯一
3.線性基二進制最高位互不相同。
4.線性基中元素互相異或，異或集合不變。
5.可以把n個數(shù)變成只有最大的數(shù)的二進制位數(shù)那么多個數(shù)
6.n個數(shù)的線性基最多只有個n個數(shù)中最大的那個數(shù)的二進制的位數(shù)個多的數(shù)
7.也就是有l(wèi)og2n個數(shù)字
8. 每一個數(shù)字出現(xiàn)的次數(shù)是相同的都是2^(n-cnt)個，cnt是線性基中元素得個數(shù)
（注意：?就是0能不能被異或出來。如果線性基的大小和原數(shù)組一樣,0是不能被異或出來的,否則可以，在求的時候要注意這一個性質(zhì)，hdu3949在求k大值的時候就用到了）
一、構(gòu)造線性基
void build(ll p) {for(int x=62;x>=0;--x){if(p&(1ll<<x))// 掃描到最高位的1(位置在位置x處)//if((p>>x)==1)或者是這種形式,都可以找出p最高位為1的位置x{if(a[x]==0)//如果ax不存在{a[x]=p;//那么a[x]就等于pbreak;//并且結(jié)束}p^=a[x];//否則p就等于 p^a[x];}}//最終p要么變?yōu)榫€性基中的一個數(shù)a[x]，要么變成了0 }//通過傳遞一組數(shù)pi,那么這組數(shù)的線性基就構(gòu)造完成了。 //而且這樣構(gòu)造出來的線性基(一組數(shù))a1 a2 a3..ax ai的最高為的1在第i位置二、求出最大值
// 1、用線性基求這組數(shù)xor出的最大值：從高往低掃ax，若異或上ax使答案變大，則異或。 ll query_max() {ll ret=0;for(int i=63;i>=0;--i){if(ret^a[i]>ret){ret^=a[i];}}return ret; }三、求出最小值
//異或的最小值、最小值即為最低位上的線性基。 ll query_min() {for(int i=0;i<=63;++i)if(a[i])return a[i];return 0; }四、倆線性基合并
//合并兩個線性基、將一個線性基暴力插入另一個線性基中就可以得到兩個原數(shù)組中合并之后的線性基了 void merge(int a1[],int a2[]) {int ret[maxn];ret=a1;for(int i=0;i<=63;++i){if(a2[i])ret.insert(a2[i]);}return ret; }五、求線性基的k小值
/* 求異或的K小值 我們要將線性基改造成每一位相互獨立。 具體操作就是如果j<i，ai的第j位是1，就將ai異或上aj 對于二進制的某一位j。只有aj的這一位是1，其他都是0。 所以查詢的時候?qū)二進制拆分，對于1的位，就異或上對應(yīng)的線性基。 最終得出的答案就是k小值。 */ void rebuild() {for(int i=62;i>=0;--i){for(int j=i-1;j>=0;--j)if(a[i]&(ll(1<<j)))a[i]^=a[j];}for(int i=0;i<=60;++i)if(a[i])p[cnt++]=a[i]; } ll quety_Kth(ll k) {ll ret=0;if(k>=(1LL<<cnt))return -1;for(int i=60;i>=0;--i)if(k&(1ll<<i))ret^=p[i];return ret; }六、查詢某一個值是否是由線性基得到
//查詢某一個值是否是由線性基得異或和得到得 void query(ll x) {for(int i=62;i>=0;--i){if((x>>i&1)&&a[i])x^=a[i];}return x==0;//成立就是可以得到 }?
總結(jié)
