向量空間
向量空間亦稱線性空間。
形式化的，我們定義一個向量空間\((P,V,+,\cdot)\)
其中 \(P\)是一個域，\(V\)是一個非空的集合，其中的集合稱作向量，同時定義兩種運算分別為向量加法和標量乘法
一個\(P\)上的向量空間\((P,V,+,\cdot)\)，需滿足以下8條公理（其中的\(u,v,w\in V\),\(a,b\)是標量）：
- \(u+(v+w)=(u+v)+w\)
- \(u+v=v+u\)
- \(\exists\mathbf{0}\)，\(s.t. \ \ v+\mathbf{0}=v\)
- \(\forall v\in V,\exists w\in V\)，\(s.t.\) \(v + w = 0\)
- \(a(u+v)=au+av\)
- \((a+b)v=av+bv\)
- \(a(bv)=(ab) v\)
- \(\exists 1,s.t. \ 1 \cdot v=v\)
基（basis）
向量空間\(V\)的基是可以張成\(V\)的一個線性無關的向量組，其中的元素稱作基向量。
異或運算&線性基
把一個數的二進制表示看成是一個向量
\[ \mathbf{a}_i=(d_n,...d_0) \]
假設向量\(\mathbf{a}_0,\mathbf{a}_1,...\mathbf{a}_m\)，的張成空間是\(S\)
定義一個向量空間\(V=(\{ 0,1\} ,S,xor,\cdot)\)
\(ps:\)這里，我們是把異或當作加法
求法
如何求出\(V\)的一個基\(\mathfrak{B}\)？
我們要做的：是掃描每一個向量\(\mathbf{a}_i\)，如果它存在于其它向量的張成空間中，就把它去掉
如何判斷每個向量能否被前面的向量張成得到？
我們利用高斯消元:
int a[MN],base[log_MN];
inline void calc()
{//n is the highest bitregister int i,j,k;for(i=0;i<=m;++i)for(j=n;~j;--j)if(a[i]>>j&1)//Scan every bit of a[I] from top to bottom{if(base[j]) a[i]^=base[j];else{//There's no vector for this bitbase[j]=a[i];/*Maintain a diagonal matrixfor(k=j-1;~k;--k) if(base[k]&&(base[j]>>k&1)) base[j]^=base[k];for(k=j+1;k<=n;++k) if(base[k]>>j&1) base[k]^=base[j];*/break;}}
}復雜度是\(O(mn)\)，若位數較多，通常采用bitset優化，復雜度是\(O(\frac{mn^2}{\omega})\)
可以發現，我們在維護一組向量\(base[]\)，滿足\(base_i\)的最高位時\(i\)
為了方便，通常只把它消成一個上三角矩陣
當然，你也可以把它消成一個類對角線矩陣，滿足每一位最多只存在于一個向量中
線性基的運用
在這里，我們不嚴謹地稱一個向量<另一個向量
其實指的是，每個向量對應的數的大小比較
查詢最值
貪心求最大值：
- 如果所求是類對角線矩陣，直接將所有向量相加即可
- 如果所求的是上三角矩陣，從高到低遍歷每個向量，若ans加上當前的向量會變大，就將其貪心的加上
最小值是線性基中最小的向量
查詢第k小值
首先在去重的前提下。
首先我們求出類對角線矩陣
那么，如果 \(k=(100101)_2\)，我們所求的即為\(base_0 +base_2+base_5\)
也就是各位所對應的數Xor起來即可
查詢和是第幾大
如果在去重的前提下，和查詢第k小差不多。
如果不在去重的前提下的話：
設\(m\)為給出數的個數， \(\mathfrak{B}\)為所求線性基
結論：每個數都出現一樣的次數，且這個次數為 \(2^{m - \vert \mathfrak{B}\vert}\)
證明：
所有不在線性基中的數的個數為 \(m - \vert \mathfrak{B}\vert\)，我們任意選擇它的一個子集 \(S\)，對于 \(S\) 中的每個數 \(v\)，有唯一的方式表達為 \(\mathfrak {B}\)中向量的線性組合。我們對于每個 \(v\)，將這個線性組合中的向量都選上（一個向量選多次可以看作是次數對\(2\)取模后的結果），兩個相同的數異或起來得到 \(0\)，所以對于每個數 \(x\)，我們都能找到至少\(2^{n - \vert \mathfrak{B}\vert}\) 種不同的選擇方案，使得異或值為 \(x\)。又因為對于每個子集 \(S\)，為了使得最終異或值為 \(x\)，選擇線性基中的向量的方案是唯一的，所以上界也是 \(2^{n - \vert \mathfrak{B}\vert}\)。
（此結論同時出現在2019/2/24 福建四校聯考中的T1）
總結
觀察大佬博客Sengxian'blog后......
線性基的題型相對比較固定，看到下面的類型基本上都是線性基了：
- 最大異或和 （例題：luogu模板題）
- 第 \(k\)大異或和/異或和是第幾大 （例題：bzoj 2844）
- 求所有異或值的和 （例題：bzoj 3811）
線性基中的題目中還用到一個技巧：
- 任意一條\(1\) 到 \(n\) 的路徑的異或和，都可以由任意一條 \(1\)到 \(n\) 路徑的異或和與圖中的一些環的異或和來組合得到。（例題：bzoj 2115）
這便是線性基的全部東西了。
Code
洛谷P3812
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
#define MN 55
ll n,base[MN],ans;
inline void insert(ll x)
{register int i,j;for(i=50;~i;--i)if(x>>i&1){if(base[i]) x^=base[i];else{base[i]=x;for(j=i-1;~j;--j)if(base[j]&&(base[i]>>j&1))base[i]^=base[j]; for(j=i+1;j<=50;++j)if(base[j]>>i&1)base[j]^=base[i];break;}}
}
int main()
{n=read();register int i;for(i=1;i<=n;++i) insert(read()); for(i=0;i<=50;++i) ans^=base[i];return 0*printf("%lld\n",ans);
} bzoj 2115 Xor
link
dfs出所有的環
求出它們的線性基
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
const int MN=200005,mN=50005,_=61;
ll a[MN],tp,dfn[mN],dind,Xor[mN],b[_];
struct edge{int to;ll w;int nex;}e[MN<<1];
int N,M,hr[mN],en;
ll ans=0;
inline void ins(int x,int y,ll w)
{e[++en]=(edge){y,w,hr[x]};hr[x]=en;e[++en]=(edge){x,w,hr[y]};hr[y]=en;
}
inline void tj(int x,int f)
{register int i;dfn[x]=++dind;for(i=hr[x];i;i=e[i].nex)if(e[i].to^f){if(!dfn[e[i].to]) Xor[e[i].to]=Xor[x]^e[i].w,tj(e[i].to,x);else a[++tp]=Xor[x]^Xor[e[i].to]^e[i].w;}
}
inline void calc()
{register int i,j,k;for(i=1;i<=tp;++i)for(j=_-1;~j;--j)if(a[i]>>j&1){if(b[j]) a[i]^=b[j];else{b[j]=a[i];break;}}ans=Xor[N];for(i=_-1;~i;--i) if((ans^b[i])>ans) ans^=b[i];
}
int main()
{N=read();M=read();int x,y;while(M--) x=read(),y=read(),ins(x,y,read());tj(1,0);calc();return 0*printf("%lld\n",ans);
}2019福建四校聯考T1
link~
首先，容斥一下，轉而求異或值為1的個數
\[ans=(2^n-1)(2^m-1)-num1\]
然后，對于一行，如果這一行的異或值不為0，它總有\(2^{m-1}\)個選法，使得選出的點的異或值是1（易證）
把每行當做一個數，我們只需要求出有哪些行的異或值為0
\[num1=2^{m-1}*(2^n-cnt0)\]
我們求出線性基，根據線性基的性質，異或值為0的個數一定是\(2^{n - \vert \mathfrak{B}\vert}\)
/*
2019/2/26 15:21
*/
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
const ll mod=998244353,MN=2005;
std::bitset<MN> a[MN],base[MN];
int N,M,B;
ll ans;
inline void calc()
{register int i,j,k;for(i=1;i<=N;++i)for(j=M-1;~j;--j)if(a[i][j]){if(base[j].count()) a[i]^=base[j];else{base[j]=a[i];break;}}for(i=0;i<M;++i) if(base[i].count()) ++B;
}
inline ll fpow(ll x,int m)
{ll r=1;for(;m;m>>=1,x=1ll*x*x%mod) if(m&1) r=1ll*r*x%mod;return r;
}
int main()
{freopen("password.in","r",stdin);freopen("password.out","w",stdout);N=read();M=read();register int i,j;for(i=1;i<=N;++i)for(j=0;j<M;++j) a[i][j]=read()==1;calc();ans=(1ll*(fpow(2,N)-1)*(fpow(2,M)-1)%mod+mod)%mod;ans-=(1ll*fpow(2,M-1)*(fpow(2,N)-fpow(2,N-B)+mod)%mod)%mod;ans+=mod,ans%=mod;return 0*printf("%lld\n",ans);
}暫時咕咕咕。
Blog來自PaperCloud，未經允許，請勿轉載，TKS！
