CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:线性基 [2020/07/26 12:38]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:线性基 [2020/10/01 10:45] (当前版本)
jxm2001
@@ 行 23: / 行 23: @@
 先将极大无关组从大到小排好(这里大小是指向量代表的二进制数的大小)，依次决定是否选择该数。
-如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大，再利用性质二，可以很容易得出第 $k$ 小异或和。
+如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大。
+再利用性质二，可以很容易得出第 $k$ 小异或和。
 只要再将极大无关组的矩阵转化为行最简矩阵，便可以满足上述条件。
@@ 行 33: / 行 35: @@
 [[https://www.luogu.com.cn/problem/P3812|洛谷p3812]]
-<hidden 查看代码>
 <code cpp>
-const int MAXN=63;
+namespace LB{//异或和从小到大排名
-LL p1[MAXN],p2[MAXN],rk;
+	const int MAXL=63;
-void Insert(LL x){//没有用高斯消元，偷了个懒
+	LL p1[MAXL],p2[MAXL],p3[MAXL];
-	for(int i=MAXN-1;i>=0;i--){
+	int rk;
-		if(x&(1LL<<i)){
+	void insert(LL x){
-			if(p1[i])
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(p1[i])
+				x^=p1[i];
+				else
+				return p1[i]=x,void();
+			}
+		}
+	}
+	LL query(LL x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x^p1[i])>x)
 			x^=p1[i];
-			else
-			return p1[i]=x,void();
 		}
+		return x;
 	}
-}
+	void rebuild(){
-void rebuild(){//转化为行最简矩阵
+		for(int i=MAXL-1;i>=0;i--){
-	for(int i=MAXN-1;i>=0;i--){
+			for(int j=i-1;j>=0;j--)
-		for(int j=i-1;j>=0;j--)
+			if((p1[i]>>j)&1)
-		if(p1[i]&(1LL<<j))
+			p1[i]^=p1[j];
-		p1[i]^=p1[j];
+		}
+		_for(i,0,MAXL)
+		if(p1[i])
+		p2[rk]=p1[i],p3[rk++]=i;
 	}
-	_for(i,0,MAXN)
+	LL kth(LL k){//第k小
-	if(p1[i])
+		if(k>=(1LL<<rk)) return -1;
-	p2[rk++]=p1[i];
+		LL ans=0;
-}
+		for(int i=MAXL-1;i>=0;i--){
-LL kth(int k){//第k小
+			if((k>>i)&1)
-	if(k>=(1LL<<rk)) return -1;
+			ans^=p2[i];
-	LL ans=0;
+		}
-	for(int i=MAXN-1;i>=0;i--){
+		return ans;
-		if(k&(1LL<<i))
-		ans^=p2[i];
 	}
-	return ans;
+	LL rank(LL x){//查询x的排名,必须保证存在异或和等于x
-}
+		LL ans=0;
-int main()
+		_for(i,0,rk)
-{
+		if((x>>p3[i])&1)
-	int n=read_int();
+		ans+=1LL<<i;
-	_for(i,0,n)
+		return ans;
-	Insert(read_LL());
+	}
-	rebuild();
+};
-	enter(kth((1LL<<rk)-1));
-	return 0;
-}
 </code>
-</hidden>
 ===== 代码练习 =====
@@ 行 351: / 行 359: @@
 			}
 		}
-	}
-	LL get_max(LL x){//结果与x以后最大化
-		for(int i=MAXL-1;i>=0;i--){
-			if((x^p1[i])>x)
-			x^=p1[i];
-		}
-		return x;
 	}
 	void rebuild(){
@@ 行 369: / 行 370: @@
 		p2[rk]=p1[i],p3[rk++]=i;
 	}
-	LL kth(LL k){//第k小
+	LL rank(LL x){
-		if(k>=(1LL<<rk)) return -1;
-		LL ans=0;
-		for(int i=MAXL-1;i>=0;i--){
-			if((k>>1)&1)
-			ans^=p2[i];
-		}
-		return ans;
-	}
-	LL rank(LL x){//查询x在异或和第k大
 		LL ans=0;
 		_for(i,0,rk)
@@ 行 399: / 行 391: @@
 </hidden>
+==== 练习题四 ====
+[[https://www.luogu.com.cn/problem/P4151|洛谷p4151]]
+=== 题意 ===
+给定一个连通图，每条路径的权值为该路径所有边的权值的异或和(路径中同一条边重复出现将重复计算贡献)。
+求结点 $1\sim n$ 的路径的最大异或和。注意图中可能存在重边和自环。
+=== 题解 ===
+考虑路径的情况一定是一条 $1\sim n$ 的简单路径(即一条边最多走一次)，再包含一些分支，每个分支经过一个环后返回。
+发现每条分支经过两次，于是不计算贡献，所以只包含了环的贡献，而由于图连通所以所有环的贡献都可以被计入。
+考虑 $\text{dfs}$ 过程中记录当前路径前缀异或和以及访问标记，得到 $\text{dfs}$ 树和若干返祖边。
+有结论任意简单环可以由若干只含一条返祖边的环通过异或得到。
+$O(n+m\log n)$ 得到所有只含一条返祖边的环的贡献，最后线性基即可得到答案。
+最后发现一开始随意选择一条 $1\sim n$ 的路径即可，因为如果该路径不是最优，则可以通过与环异或修改为最优路径。
+<hidden 查看代码>
+<code cpp>
+namespace LB{
+	const int MAXN=63;
+	LL p1[MAXN],p2[MAXN],rk;
+	void insert(LL x){
+		for(int i=MAXN-1;i>=0;i--){
+			if(x&(1LL<<i)){
+				if(p1[i])
+				x^=p1[i];
+				else
+				return p1[i]=x,void();
+			}
+		}
+	}
+	LL query(LL x){
+		for(int i=MAXN-1;i>=0;i--){
+			if((x^p1[i])>x)
+			x^=p1[i];
+		}
+		return x;
+	}
+}
+const int MAXN=5e4+5,MAXM=1e5+5;
+struct Edge{
+	int to,next;
+	LL w;
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt,dfn[MAXN],dfs_t;
+void Insert(int u,int v,LL w){
+	edge[++edge_cnt]=Edge{v,head[u],w};
+	head[u]=edge_cnt;
+}
+LL dfs_s[MAXN];
+void dfs(int u,LL s){
+	dfn[u]=++dfs_t;
+	dfs_s[u]=s;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(!dfn[v])
+		dfs(v,edge[i].w^s);
+		else if(dfn[v]<=dfn[u])
+		LB::insert(s^edge[i].w^dfs_s[v]);
+	}
+}
+int main()
+{
+	int n=read_int(),m=read_int(),u,v;
+	LL w;
+	while(m--){
+		u=read_int(),v=read_int(),w=read_LL();
+		Insert(u,v,w);
+		Insert(v,u,w);
+	}
+	dfs(1,0LL);
+	enter(LB::query(dfs_s[n]));
+	return 0;
+}
+</code>
+</hidden>
+==== 练习题五 ====
+[[https://www.luogu.com.cn/problem/CF1299D|CF1299D]]
+=== 题意 ===
+给定一个边权图，要求删除一些与结点 $1$ 相邻的边，使得不存在路径满足下述条件：
+  - 以 $1$ 号节点为起点，$1$ 号节点为终点
+  - 此路径经过的所有边的边权异或和为 $0$
+  - 其至少经过了一条边奇数次
+输出所有满足条件的方案数模 $10^9+7$ 的结果。
+保证图中所有边权 $w\in [0,31]$，不存在重边和自环且不存在一个长度 $\gt 3$ 的简单环经过了 $1$ 号点。
+=== 题解 ===
+考虑将点 $1$ 删去，得到若干连通块，由于不存在一个长度 $\gt 3$ 的简单环经过了 $1$ 号点，于是每个连通块仅可能有 $1\sim 2$ 个点与点 $1$ 相邻。
+考虑求出每个连通块的所有环的异或和构成的线性基，并且先不妨假设所有连通块都只有一条边与 $1$ 点相连。
+如果该线性基在建立过程中插入失败，说明部分环线性相关。则该连通块与 $1$ 相邻后一定会出现非法路径，于是该连通块与 $1$ 的连边必须删去。
+对于剩下的连通块，只需要保证所有选择的连通块的线性基在相互合并时不会出现线性相关即可。
+考虑对所有线性基的最简形式进行编号，同时预处理任意两个线性基合并得到的新线性基的编号。
+设 $\text{dp}(i,j)$ 表示只考虑前 $i-1$ 个连通块时，选择部分连通块的线性基合并最后得到线性基编号为 $j$ 的方案数。
+同时记 $id_i$ 表示第 $i$ 个连通块的线性基，于是不难得出状态转移方程
+$$\text{dp}(i,\text{Merge}(id_i,k))\gets \text{dp}(i-1,k)$$
+如果该连通块与点 $1$ 有 $2$ 条边，则首先可以任意选择保留一条连通，于是可以产生双倍贡献。
+另外如果保留两条连边，则记这两条连边的除 $1$ 外的端点为 $v_1,v_2$，则考虑先选择 $1\to v_1\to v_2\to 1$，然后再异或上一些环。
+于是可以得到新的线性基为原连通块的线性基异或上这三条边，然后考虑新线性基对 $\text{dp}$ 的贡献。
+最后发现最简线性基共 $k=374$ 种，于是总时间复杂度 $O(kn+k^2+32k\log 32)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=400,MAXV=1<<15,MAXL=5,Mod=1e9+7;
+struct Edge{
+	int to,w,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+struct LB{
+	int p[MAXL];
+	bool insert(int x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(p[i])
+				x^=p[i];
+				else{
+					p[i]=x;
+					_for(j,0,i){
+						if(p[j]&&((p[i]>>j)&1))
+						p[i]^=p[j];
+					}
+					_for(j,i+1,MAXL){
+						if((p[j]>>i)&1)
+						p[j]^=p[i];
+					}
+					return true;
+				}
+			}
+		}
+		return false;
+	}
+	int query(int x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x^p[i])>x)
+			x^=p[i];
+		}
+		return x;
+	}
+	int encode(){
+		return p[0]|(p[1]<<1)|(p[2]<<3)|(p[3]<<6)|(p[4]<<10);
+	}
+	LB(){mem(p,0);}
+}lb[MAXM];
+int Hash[MAXV],Merge[MAXM][MAXM],lb_cnt;
+void dfs(LB u){
+	if(!Hash[u.encode()]){
+		lb[++lb_cnt]=u;
+		Hash[u.encode()]=lb_cnt;
+		_for(i,1,32){
+			LB temp=u;
+			if(temp.insert(i))
+			dfs(temp);
+		}
+	}
+}
+void Pre_merge(){
+	Merge[1][1]=1;
+	_rep(i,1,lb_cnt)
+	_rep(j,i+1,lb_cnt){
+		LB temp=lb[i];
+		bool flag=true;
+		_for(k,0,MAXL){
+			if(lb[j].p[k]&&!temp.insert(lb[j].p[k])){
+				flag=false;
+				break;
+			}
+		}
+		if(flag)
+		Merge[i][j]=Merge[j][i]=Hash[temp.encode()];
+	}
+}
+int block_root[MAXN],block_id[MAXN],cyc_s[MAXN],block_cnt;
+bool fail[MAXN],is_cyc[MAXN];
+LB block_lb[MAXN];
+int dfn[MAXN],dfs_t,dis[MAXN];
+int dp[2][MAXM];
+void dfs2(int u,int fa,int s){
+	dfn[u]=++dfs_t,dis[u]=s;
+	block_id[u]=block_cnt;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==1||v==fa)continue;
+		if(!dfn[v])
+		dfs2(v,u,s^edge[i].w);
+		else if(dfn[v]<dfn[u])
+		fail[block_cnt]|=!block_lb[block_cnt].insert(s^dis[v]^edge[i].w);
+	}
+}
+int main()
+{
+	dfs(LB());
+	Pre_merge();
+	int n=read_int(),m=read_int();
+	while(m--){
+		int u=read_int(),v=read_int(),w=read_int();
+		Insert(u,v,w);
+		Insert(v,u,w);
+	}
+	for(int i=head[1];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(!block_id[v]){
+			block_root[++block_cnt]=v;
+			dfs2(v,0,edge[i].w);
+		}
+		else{
+			int idx=block_id[v];
+			is_cyc[idx]=true;
+			for(int j=head[v];j;j=edge[j].next){
+				int vv=edge[j].to;
+				if(vv==block_root[idx]){
+					cyc_s[idx]=dis[vv]^edge[j].w^edge[i].w;
+					break;
+				}
+			}
+		}
+	}
+	int pos=0;
+	dp[pos][1]=1;
+	_rep(i,1,block_cnt){
+		if(fail[i])continue;
+		int h=Hash[block_lb[i].encode()];
+		pos=!pos;
+		_rep(j,1,lb_cnt)
+		dp[pos][j]=dp[!pos][j];
+		if(!is_cyc[i]){
+			_rep(j,1,lb_cnt){
+				if(Merge[j][h])
+				dp[pos][Merge[j][h]]=(dp[pos][Merge[j][h]]+dp[!pos][j])%Mod;
+			}
+		}
+		else{
+			bool flag=block_lb[i].insert(cyc_s[i]);
+			int h2=Hash[block_lb[i].encode()];
+			_rep(j,1,lb_cnt){
+				if(Merge[j][h])
+				dp[pos][Merge[j][h]]=(dp[pos][Merge[j][h]]+2LL*dp[!pos][j])%Mod;
+				if(flag&&Merge[j][h2])
+				dp[pos][Merge[j][h2]]=(dp[pos][Merge[j][h2]]+dp[!pos][j])%Mod;
+			}
+		}
+	}
+	int s=0;
+	_rep(i,1,lb_cnt)
+	s=(s+dp[pos][i])%Mod;
+	enter(s);
+	return 0;
+}
+</code>
+</hidden>
+==== 练习题六 ====
+[[http://acm.hdu.edu.cn/showproblem.php?pid=6579|HDU6578]]
+=== 题意 ===
+给定一个长度为 $n$ 的序列，支持下述操作：
+  - 询问区间 $[l,r]$ 的所有子序列的最大异或和
+  - 在序列末尾添加一个数
+强制在线。
+=== 题解 ===
+考虑对每个 $r$，贪心维护区间 $[1,r]$ 的线性基每个位的数值和代表元位置。
+具体来说，对每个新插入的数，从高位到低位考虑是否可以将该值插入。
+如果该位置没有数则直接插入，否则如果该位置的代表元位置相对于插入数的位置偏左，则将该位置的代表元置换出来。
+对区间 $[l,r]$，考虑 $r$ 维护的线性基当前位的代表元位置是否不小于 $l$ 即可。时空间复杂度 $O((n+q)\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+namespace LB{
+	const int MAXL=31;
+	int p1[MAXL],p2[MAXN][MAXL];
+	int pos1[MAXL],pos2[MAXN][MAXL];
+	void clear(){
+		mem(p1,0);mem(p2,0);
+		mem(pos1,0);mem(pos2,0);
+	}
+	void insert(int x,int pos){
+		int r=pos;
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(!p1[i]){
+					p1[i]=x;
+					pos1[i]=pos;
+					break;
+				}
+				else if(pos1[i]<pos){
+					swap(p1[i],x);
+					swap(pos1[i],pos);
+				}
+				x^=p1[i];
+			}
+		}
+		_for(i,0,MAXL){
+			p2[r][i]=p1[i];
+			pos2[r][i]=pos1[i];
+		}
+	}
+	LL query(int l,int r){
+		int ans=0;
+		for(int i=MAXL-1;i>=0;i--){
+			if(pos2[r][i]>=l&&(ans^p2[r][i])>ans)
+			ans^=p2[r][i];
+		}
+		return ans;
+	}
+};
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int(),q=read_int(),lastans=0;
+		LB::clear();
+		_rep(i,1,n)
+		LB::insert(read_int(),i);
+		while(q--){
+			int opt=read_int();
+			if(!opt){
+				int l=(read_int()^lastans)%n+1,r=(read_int()^lastans)%n+1;
+				if(l>r)swap(l,r);
+				enter(lastans=LB::query(l,r));
+			}
+			else
+			LB::insert(read_int()^lastans,++n);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 练习题七 ====
+[[https://ac.nowcoder.com/acm/contest/884/B|2019牛客暑期多校训练营（第四场）B]]
+=== 题意 ===
+给定 $n$ 个集合和 $q$ 个询问，每个集合给定 $sz_i$ 个元素。
+每次询问对区间 $[l,r]$ 的每个集合是否都存在子集异或和为 $x$。
+=== 题解 ===
+考虑线段树求解，于是问题转化为如何维护两个线性基的交。
+线性空间 $v_1,v_2$ 的交 $v_3$ 仍为线性空间，仍然可以用线性基表示，且满足 $v_3$ 的线性基可以用 $v_1,v_2$ 的线性基表示。
+不妨记 $v_1$ 的线性基为 $a$，记 $v_2$ 的线性基为 $b$，记 $v_3$ 的线性基为 $c$。
+考虑初始空间为 $v_1$，然后依次将 $v_2$ 的线性基插入，如果插入出现线性相关，则有
+$$
+a_{x_1}\oplus a_{x_2}\oplus\cdots \oplus a_{x_{t_1}}\oplus b_{y_1}\oplus b_{y_2}\oplus\cdots \oplus b_{y_{t_2}}=b_i
+$$
+移项，得
+$$
+c=a_{x_1}\oplus a_{x_2}\oplus\cdots \oplus a_{x_{t_1}}=b_{y_1}\oplus b_{y_2}\oplus\cdots \oplus b_{y_{t_2}}\oplus b_i
+$$
+于是将新得到的 $c$ 插入 $v_3$ 即可。注意在插入 $v_2$ 过程中维护线性基每个位的 $v_1$ 空间的贡献。时间复杂度 $O((n+q)\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,MAXL=32;
+struct LB{
+	LL p[MAXL];
+	void insert(LL x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(p[i])
+				x^=p[i];
+				else
+				return p[i]=x,void();
+			}
+		}
+	}
+	bool query(LL x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(p[i])
+				x^=p[i];
+				else
+				return false;
+			}
+		}
+		return true;
+	}
+}a[MAXN],s[MAXN<<2];
+int lef[MAXN<<2],rig[MAXN<<2];
+void push_up(int k){
+	LB t=s[k<<1],v1=s[k<<1],v2=s[k<<1|1];
+	_for(i,0,MAXL){
+		if(v2.p[i]){
+			LL x=v2.p[i],y=0;
+			bool flag=true;
+			for(int j=MAXL-1;j>=0;j--){
+				if((x>>j)&1){
+					if(t.p[j]){
+						x^=t.p[j];
+						y^=v1.p[j];
+					}
+					else{
+						t.p[j]=x;
+						v1.p[j]=y;
+						flag=false;
+						break;
+					}
+				}
+			}
+			if(flag)
+			s[k].insert(y);
+		}
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	int M=L+R>>1;
+	if(L==R)
+	return s[k]=a[M],void();
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+bool query(int k,int L,int R,LL x){
+	if(L>rig[k]||R<lef[k])
+	return true;
+	if(L<=lef[k]&&rig[k]<=R)
+	return s[k].query(x);
+	int M=L+R>>1;
+	return query(k<<1,L,R,x)&&query(k<<1|1,L,R,x);
+}
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n){
+		int cnt=read_int();
+		while(cnt--)
+		a[i].insert(read_LL());
+	}
+	build(1,1,n);
+	while(q--){
+		int l=read_int(),r=read_int();
+		if(query(1,l,r,read_LL()))
+		puts("YES");
+		else
+		puts("NO");
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具