线性基训练与总结

今天药忘吃喽~ 2021-09-30 06:10 342阅读 0赞

# 线性基 #

## 我们先考虑基的一些定义和性质。 ##

*  唯一表示
 *  线性无关
 *  极小生成集

acm中的线性基一般是基于异或运算下的。

根据第一条，我们可以解决一系列算贡献的题目。

根据第二条，我们可以知道任一基里的元素不能被其他元素异或得到，进而我们得到基里的元素不能通过异或得到0。

根据第三条，线性基的任何真子集不能张成原线性空间。

## 两种矩阵 ##

*  对角矩阵
 *  上三角矩阵

对角矩阵是通过高斯消元使1只存在主对角线上，可以动态维护，或者先生成上三角矩阵再rebuild

在一些题目有一些细微的差别，比如查最大异或和，上三角需要贪心，而对角矩阵只需要从高位一直异或下去（当然这个从高位异或下来的操作本身也是贪心）。

除了查询第K大时，消成对角矩阵外，一般上三角矩阵就够用了。

## 查询最大异或和 ##

### [P3812 【模板】线性基][P3812] ###

## 查询第K大 ##

### HDOJ 3949 ###

注意一些边际情况，以及线性基不能异或得到0

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 1e4 + 1000;
    
    int n,m;
    ll q;
    struct LB
    { 
    	ll p[64],o[64];
    	int cnt;
    	void init()
    	{ 
    		rep(i,0,64)
    		p[i] = o[i] = 0;
    		cnt = 0;
    	}
    	bool ins(ll x)
    	{ 
    		per(i,0,64)
    		{ 
    			if((x >>(ll)i) & 1)
    			{ 
    				if(!p[i])
    				{ 
    					p[i] = x;
    					cnt++;
    					return true;
    				}
    				x ^= p[i];
    			}
    		}
    		return false;
    	}
    	void rebulid()
    	{ 
    		per(i,0,64)
    		{ 
    			per(j,0,i)
    			{ 
    				if(p[i] & (1ll<<j))
    				{ 
    					p[i] ^= p[j];
    				}
    			}
    		}
    		int tmp = 0;
            rep(i,0,63)
               if(p[i])
                  o[tmp++]=p[i];
    	}
    
    	ll query(ll x)
    	{ 
    		if(cnt != n)
    		{ 
    			x--;
    		}//注意0的情况
    		ll tmp = 1ll << cnt;
    		if(x >= tmp)
    		{ 
    			return -1;
    		}
    		ll ans = 0;
    		rep(i,0,64)
    		{ 
    			if((x>>(ll)i)&1)
    			{ 
    				ans ^= o[i];
    			}
    		}
    		return ans;
    	}
    };
    int T;
    
    ll a[maxn];
    int main(int argc, char const *argv[])
    { 
    	scanf("%d",&T);
    	int cas = 1;
    	while(T--)
    	{ 
    		LB ba;
    		ba.init();
    		scanf("%d",&n);
    		ll ans = 0;
    		rep(i,0,n)
    		{ 
    			scanf("%lld",&a[i]);
    			ba.ins(a[i]);
    		}
    		ba.rebulid();
    		printf("Case #%d:\n",cas++);
    		scanf("%d",&m);
    		rep(i,0,m)
    		{ 
    			scanf("%lld",&q);
    			printf("%lld\n",ba.query(q));
    		}
    
    	}
    	return 0;
    }

## 查询区间最大异或和 ##

### HDU-6579 Operation ###

需要对每一个位置维护一个线性基，插入操作为继承上一个点的线性基并插入当前点。  
考虑贪心，尽可能使组成线性基的点更靠近R。  
g\[i\]存组成线性基第i个的位置，从高位开始尽可能使它靠近R

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 1e6+100;
    
    struct LB
    { 
    	ll p[33];
    	int g[33];//存位置
    	void ins(ll x,int pos)
    	{ 
    		 per(i,0,30)
    		 { 
    		 	if((x>>i) & 1)
    		 	{ 
    		 		if(p[i])
    		 		{ 
    		 			if(g[i] <= pos)
    		 			{ 
    		 				x ^= p[i];
    		 				p[i] ^= x;
    		 				swap(g[i],pos);
    		 			}
    		 			else
    		 				x ^= p[i];
    		 		}
    		 		else
    		 		{ 
    		 			p[i] = x;
    		 			g[i] = pos;
    		 			break;
    		 		}
    		 	}
    		 }
    	}	
    	ll query(int l)
    	{ 
    		ll res = 0;
    		per(i,0,30)
    		{ 
    			if(g[i] >= l)
    			{ 
    				res = max(res,res^p[i]);
    			}
    		}
    		return res;
    	}
    } base[maxn];
    
    int n,m;
    
    int gao(int x,int lastans)
    { 
    	return (x^lastans) % n + 1;
    }
    
    int T;
    int x;
    
    int main(int argc, char const *argv[])
    { 
    	// ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	scanf("%d",&T);
    	while(T--)
    	{ 
    		scanf("%d%d",&n,&m);
    		rep(i,1,n+1)
    		{ 
    			scanf("%d",&x);
    			base[i] = base[i-1];
    			base[i].ins(x,i);
    		}
    		ll ans = 0;
    		int l,r;
    		while(m--)
    		{ 
    			int op;
    			scanf("%d",&op);
    			if(!op)
    			{ 
    				scanf("%d%d",&l,&r);
    				l = gao(l,ans);r=gao(r,ans);
    				if(l>r) swap(l,r);
    				ans = base[r].query(l);
    				printf("%lld\n",ans);
    			}
    			else
    			{ 
    				n++;
    				scanf("%d",&l);
    				base[n] = base[n-1];
    				base[n].ins(l^ans,n);
    			}
    		}
    	}
    	return 0;
    }

## 算贡献 ##

### P3857 \[TJOI2008\]彩灯 ###

根据唯一表示，答案为 2 c n t 2^\{cnt\} 2cnt

### cf 959F ###

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define de(c) cout << #c << " = " << c << endl
    #define dd(c) cout << #c << " = " << c << " "
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    const int maxn = 1e5 + 100;
    
    struct LB
    { 
    	ll p[22];
    	int cnt;
    	void init()
    	{ 
    		rep(i,0,22)
    		{ 
    			p[i] = 0;
    		}
    		cnt = 0;
    	}
    	void ins(ll x)
    	{ 
    		per(i,0,22)
    		{ 
    			if((x>>i)&1)
    			{ 
    				if(!p[i])
    				{ 
    					p[i] = x;
    					cnt++;
    					return;
    				}
    				x ^= p[i];
    			}
    		}
    	}
    	bool gao(ll x)
    	{ 
    		per(i,0,22)
    		{ 
    			if((x>>i)&1)
    			{ 
    				if(!p[i])
    				{ 
    					return false;
    				}
    				x ^= p[i];
    			}
    		}
    		return true;
    	}
    } L;
    
    int n,q;
    ll a[maxn];
    
    struct node
    { 
    	int pos,id;
    	ll x;
    } Q[maxn];
    
    bool cmp(node a,node b)
    { 
    	return a.pos < b.pos;
    }
    
    ll ans[maxn];
    int main(int argc, char const *argv[])
    { 
    	L.init();
    	scanf("%d%d",&n,&q);
    	rep(i,0,n)
    	{ 
    		scanf("%lld",&a[i]);
    	}
    	rep(i,0,q)
    	{ 
    		scanf("%d%d",&Q[i].pos,&Q[i].x);
    		Q[i].pos-=1;
    		Q[i].id = i;
    	}
    	sort(Q,Q+q,cmp);
    	int pos = 0;
    	rep(i,0,q)
    	{ 
    		// de(Q[i].pos);
    		// de(Q[i].x);
    		while(pos <= Q[i].pos) L.ins(a[pos++]);
    		if(L.gao(Q[i].x))
    		{ 
    			ans[Q[i].id] = powmod(2,Q[i].pos+1-L.cnt);
    		}
    	}
    	rep(i,0,q)
    	{ 
    		printf("%lld\n", ans[i]);
    	}
    	return 0;
    }

### 2019牛客暑期多校训练营（第一场） - H XOR（线性基） ###

[题解][Link 1]

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int mod = 1e9 + 7;
    typedef long long ll;
    
    ll qp(ll a, ll n)
    { 
        if(n < 0) return 0;
        ll ans = 1;
        for(;n ; (a *= a) %= mod, n >>= 1) if(n & 1) (ans *= a) %= mod;
        return ans;
    }
    
    ll v;
    
    struct LinearBasis
    { 
    	ll d[63], o[63];   //原矩阵，o并不是对角矩阵，只是消成只保存最高位的1，便于统计答案
    
    	void init()
    	{ 
    		for(int i = 0; i < 64; i ++) d[i] = o[i] = 0;
    		v = 0;
    	}
    
    	bool ins(ll x)
    	{ 
    	    ll tmp = 0;
    	    bool flag = false;
    		for(int i = 62; i >= 0; i --)
    		{ 
    			if((x >> i) & 1)
    			{ 
    				if(!d[i]) d[i] = x, o[i] = tmp | (1ll << i), flag = true;
    				x ^= d[i]; tmp ^= o[i];
    				if(!x) break;
    			}
    		}
    		if(!flag) v |= tmp;
    		return flag;
    	}
    }L;
    
    int main()
    { 
        int n;
        while(scanf("%d", &n) != EOF)
        { 
            L.init();
            ll x, ans = 0, cnt = 0;
            for(int i = 0; i < n; i ++)
            { 
                scanf("%lld", &x);
                if(!L.ins(x)) ans ++;
            }
            for(int i = 0; i < 63; i ++)
            { 
                if(L.d[i]) cnt ++;
                if((1ll << i) & v) ans ++;
            }
            printf("%lld\n", ans * qp(2, n - cnt - 1) % mod);
        }
        return 0;
    }

## 许多其他贪心 ##

### P4570 \[BJWC2011\]元素 ###

根据线性基中异或和不存在0去贪心

[P3812]: https://www.luogu.org/problem/P3812
[Link 1]: https://v-verly.github.io/2019/07/19/Nowcoder-Multi-University-2019-Round1-H/