CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:线性基 [2020/09/30 19:23]
jxm2001 [练习题五]
+++ 2020-2021:teams:legal_string:jxm2001:线性基 [2020/10/01 10:45] (当前版本)
jxm2001
@@ 行 23: / 行 23: @@
 先将极大无关组从大到小排好(这里大小是指向量代表的二进制数的大小)，依次决定是否选择该数。
-如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大，再利用性质二，可以很容易得出第 $k$ 小异或和。
+如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大。
+再利用性质二，可以很容易得出第 $k$ 小异或和。
 只要再将极大无关组的矩阵转化为行最简矩阵，便可以满足上述条件。
@@ 行 494: / 行 496: @@
 考虑将点 $1$ 删去，得到若干连通块，由于不存在一个长度 $\gt 3$ 的简单环经过了 $1$ 号点，于是每个连通块仅可能有 $1\sim 2$ 个点与点 $1$ 相邻。
-考虑求出每个连通块的所有环的异或和构成的线性基。
+考虑求出每个连通块的所有环的异或和构成的线性基，并且先不妨假设所有连通块都只有一条边与 $1$ 点相连。
 如果该线性基在建立过程中插入失败，说明部分环线性相关。则该连通块与 $1$ 相邻后一定会出现非法路径，于是该连通块与 $1$ 的连边必须删去。
-对于剩下的连通块，如果
+对于剩下的连通块，只需要保证所有选择的连通块的线性基在相互合并时不会出现线性相关即可。
 考虑对所有线性基的最简形式进行编号，同时预处理任意两个线性基合并得到的新线性基的编号。
-设 $\text{dp}(i,j)$ 表示只考虑前 $i-1$ 个连通块时，
+设 $\text{dp}(i,j)$ 表示只考虑前 $i-1$ 个连通块时，选择部分连通块的线性基合并最后得到线性基编号为 $j$ 的方案数。
-考虑求出每个连通块代表的线性基，如果该连通块的线性基在建立过程中线性相关，则该连通块与 $1$ 相邻的边必须删去。
+同时记 $id_i$ 表示第 $i$ 个连通块的线性基，于是不难得出状态转移方程
-否则，如果该连通块与点 $1$ 只有 $1$ 条边
+$$\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

用户工具

站点工具

页面工具