cf1299d Around the world 欧拉子图, 线性基

本场其他题目

A: 签到

B: 几何结论题，如果学过闵科夫斯基和一眼就能看出来

C: 看起来需要前缀平均值最大，像个数据结构题。实际上观察会发现答案其实就是数列的下凸包。

题意

给定一幅带权无向连通图，n,m<1e5, wi<32，且满足：1号点不包含于长度大于3的环中
求删去与1相邻的一些边，使1不存在于任何权值异或和为0的路径中(可为非简单路径，但至少需要经过一条边奇数次)，问方案数

题解

注意题意描述的是“1号点在路径中”，而非简单路可以经过多次，实际上异或结果可能相当于不包括1号点。

首先任意欧拉回路可表示为若干个简单环的异或。于是想到把图看成在树上加非树边，每个非树边对应一个环。把32种可能的边权视为Z2上的5维向量，则每个环连接不出0等价于所有的环构成一线性基(没有线性相关)。代码实现中可标记出所有的基向量。

然后，考虑到限制条件就是1的子节点由两种类型的子图构成，互不相交。一种连出一个单独的节点，一种是连一个三元环。第一种中，若子图存在线性相关，则必须删掉，否则若不删掉则可加入。第二种中，分别考虑不删、删一边、都删的情况。

然后问题转化为：统计有多少种删边方式使剩下的线性空间均线性无关。然而边数达到2e5，但维数却只有5。启示我们应该从线性基这边进行状态压缩统计。实际上，5维布尔向量只有374种不同的线性子空间(或者说只有374种本质不同的线性基)，所以可以预处理出每种线性空间和它们两两的和空间。然后就是个计数dp了。

更多关于线性基的解释可以看 http://101.132.170.22/wordpress/?p=669

dp[i,j]表示加入第i个块时，形成第j种基的方案数。
于是对于i号块对应的基X，只要枚举与X不相交的Y，那么X和Y直和对应的空间方案数dp[i, X+Y]+=dp[i-1, Y]
dp复杂的O(n*374)，暴力预处理空间和复杂度O(374*374*32*32)。

```
/*
```
```
Author: WangXP
```
```
Date:
```
```
 */
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
#define pb push_back
```
```
typedef long long ll;
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
#define icc(i,n) for (int i=1;i<=n;i++)
```

#define rep(i,a,b) for (int i=a;i<b;i++)

#define rpp(i,a,b) for (int i=a;i<=b;i++)

#define dec(i,n) for (int i=n-1;i>=0;i--)

```
#define dcc(i,n) for (int i=n;i;i--)
```
```
ll rd(){
```
```
	ll x=0,f=1;char c=getchar();
```

	while (!isdigit(c) && c!='-') c=getchar();

```
	if (c=='-') f=-1,c=getchar();
```

	while (isdigit(c)) x=x*10+c-'0',c=getchar();

```
	return x*f;
```
```
}
```
```
 
```
```
const int N=200010, P=1e9+7;
```
```
 
```
```
int n,m;
```
```
 
```
```
struct Edge{
```
```
	int to, nxt, w;
```
```
}ed[N];
```
```
int head[N],ecnt=1;
```
```
 
```
```
void added(int a, int b, int c){
```
```
	ed[++ecnt]={b,head[a],c};
```
```
	head[a]=ecnt;
```
```
	ed[++ecnt]={a,head[b],c};
```
```
	head[b]=ecnt;
```
```
}
```
```
 
```
```
void add(int &a, int b){
```
```
	a+=b;
```
```
	if (a>=P) a-=P;
```
```
}
```
```
 
```
```
typedef unsigned int ui;
```
```
map<ui,int> id; ui state[N]; int ST;
```
```
ui can[N], can2[N];
```

int mg[400][400], f[400], new_f[400],in[N];

```
int sxor[N],sxor2[N];
```
```
 
```
```
//search all linear space of Z_2^5
```
```
void dfs_state(ui v){
```
```
	if (id.count(v)) return;
```
```
	id[v]=++ST; state[ST]=v;
```

	for(int i=1;i<32;i++) if (!(v>>i&1)){ //try add vector i

```
		ui w=v;
```
```
		for (int j=0;j<32;j++) //add element 
```
```
			if(v>>j&1) w|=1u<<(i^j); 
```
```
		dfs_state(w);
```
```
	}
```
```
}
```

ui get(int x){return x==0?0:1u<<x|1;} //single vec space with zero vector

```
ui meg(ui a, ui b){
```

	if (!a||!b) return 0; //bad space, already has co-linear

	if ((a>>1)&(b>>1)) return 0; //no intersection

```
	ui ret=0; //direct sum
```
```
	for (int i=0;i<32;i++)
```
```
		for (int j=0;j<32;j++)
```

			if ((a>>i&1) && (b>>j&1)) ret|=1u<<(i^j);

```
	return ret;
```
```
}
```
```
 
```
```
int fa[N],dep[N];
```
```
void dfs(int u, int pa, int rt){
```
```
	dep[u]=dep[pa]+1; fa[u]=pa;
```

	for (int e=head[u],v;v=ed[e].to,e;e=ed[e].nxt) if(v!=pa){

		if (!dep[v]) sxor[v]=sxor[u]^ed[e].w, dfs(v,u,rt==1?v:rt);

```
		else if (dep[v]<dep[u]){
```

			if (v==1) in[fa[u]]=1, sxor2[rt]=sxor[u]^ed[e].w; //label 3-circle edge

			else can[rt]=meg(can[rt],get(ed[e].w^sxor[v]^sxor[u]));

```
		}
```
```
	}
```
```
}
```
```
 
```
```
int main(){
```
```
	dfs_state(1);
```
```
	//cout<<ST<<'\n';
```
```
	n=rd(),m=rd();
```

	for (int i=1,a,b;i<=m;i++) a=rd(),b=rd(),added(a,b,rd());

	icc(i,n) can[i]=1; //init space with zero vector

```
	dfs(1,0,1); f[1]=1;
```
```
	icc(i,ST) icc(j,ST)
```
```
		mg[i][j]=id[meg(state[i],state[j])];
```

	for(int e=head[1],v;v=ed[e].to,e;e=ed[e].nxt){ //dp

```
		if (fa[v]!=1) continue;
```
```
		memset(new_f,0,sizeof new_f);
```
```
		if (in[v]){ //3-circle i-node
```
```
			can2[v]=meg(can[v],get(sxor2[v]));
```
```
			//cout<<can[v]<<' '<<can2[v]<<'\n';
```

			can[v]=id[can[v]]; can2[v]=id[can2[v]];

```
			icc(i,ST){
```
```
				if (!f[i]) continue;
```
```
				add(new_f[i],f[i]);
```

				add(new_f[mg[i][can[v]]],2ll*f[i]%P);

```
				add(new_f[mg[i][can2[v]]],f[i]);
```
```
			}
```
```
		}
```
```
		else{
```
```
			//cout<<sxor[v]<<' '<<can[v]<<'\n';
```
```
			can[v]=id[can[v]];
```
```
			icc(i,ST){
```
```
				add(new_f[i],f[i]);
```
```
				add(new_f[mg[i][can[v]]],f[i]);
```
```
			}
```
```
		}
```
```
		swap(f,new_f);
```
```
	}
```
```
	int ans=0;
```
```
	icc(i,ST) add(ans,f[i]);
```
```
	cout<<ans<<'\n';
```
```
	return 0;
```
```
}
```

fffasttime

cf1299d Around the world 欧拉子图, 线性基

本场其他题目

题意

题解

发表评论取消回复

本场其他题目

题意

题解

发表评论 取消回复

发表评论取消回复