• 欢迎光临~

【CF1299D】Around the World(线性基)

开发技术 开发技术 2022-10-28 次浏览

题意:

给定一张 (n) 个点 (m) 条边的无向连通图,边带权,保证不存在一个长度 (>3) 的简单环经过了 (1) 号点。请求出有多少种方案删除若干条与 (1) 号点相连的边,使得不存在任何一条路径(不一定是简单路径)满足:

  • (1) 号点为起点,以 (1) 号点为终点。
  • 路径经过的所有边的边权异或和为 (0)(经过多次异或多次)。
  • 图上至少有一条边被该路径经过了奇数次。

(n,mleq 10^5)(wleq 31)

题解:

先考虑假设图确定了应该怎么做。这是经典问题(最大 XOR 路径),相当于在图上选若干个环(不一定是简单环),使得它们异或和为 (0)。做法是先选出一些代表环,使得任意一种选法都能被某些代表环异或出来。发现我们只需要把 dfs 树上返祖边所对应的环作为代表环即可,然后把它们的权值插入线性基内,看是否线性相关。

对于这一题,我们可以先把与 (1) 相连的所有边断掉,这样会形成若干个连通块。那么相当于考虑每个连通块是否与 (1) 相连,且相连的边数是多少(只可能是 (1)(2))。那么可以考虑逐个加入连通块并 DP,但关键是线性基怎么维护。

一个神奇的地方是大小为 (5) 的本质不同线性基只有 (374) 种,我们为它们标号并暴力记录:设 (f_{i,j}) 表示考虑了前 (i) 个连通块,所形成的图的线性基为第 (j) 个线性基的方案数。

转移过程中考虑新加入一个连通块,连通块内的线性基我们可以预处理,而连通块外的环至多只有一个(注意不可能有环跨过两个连通块,所以唯一没考虑的环只可能是连通块与 (1) 号点之间的那个三元环),我们对它再单独加入线性基即可。而线性基合并的结果我们也可以预处理。

时间复杂度 (O(nc))

有关大小为 (n) 的本质不同线性基数量:

考虑长度为 (n) 的所有二进制数,它们构成了一个大小为 (2^n)(n) 维空间。而一个线性基实际上对应的是这个 (n) 维空间中的一个子空间。

先枚举这个子空间的维数 (k),然后考虑统计本质不同的 (k) 维子空间的数量。考虑在 (n) 维空间中有序选取 (k) 个线性无关的向量,它们对应一个 (k) 维的子空间。而每一个 (k) 维子空间被计算的次数同样就是这个 (k) 维空间内有序选取 (k) 个线性无关向量的方案数。

所以本质不同的 (k) 维子空间的数量为:(注意不能选零向量)

[frac{(2^n-1)(2^n-2)cdots(2^n-2^{k-1})}{(2^k-1)(2^k-2)cdots(2^k-2^{k-1})}=prod_{i=0}^{k-1}frac{2^n-2^i}{2^k-2^i} ]

实际上,这玩意有个名字,叫 q-二项式系数,记作 (dbinom{n}{k}_q),这里是 (q=2) 的情况。

于是大小为 (n) 的本质不同线性基数量为:

[sum_{k=0}^{n}binom{n}{k}_2 ]

这玩意只有组合意义的结果,但那玩意看起来很高深。可以给出一个在 (nleq 10) 时比较好记的近似:(n^{n-2}) 的几倍。

#include<bits/stdc++.h>

#define N 100010

using namespace std;

namespace modular
{
	const int mod=1000000007;
	inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y){return 1ll*x*y%mod;}
	inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
	inline void Dec(int &x,int y){x=x-y<0?x-y+mod:x-y;}
	inline void Mul(int &x,int y){x=1ll*x*y%mod;}
	inline int poww(int a,int b){int ans=1;for(;b;Mul(a,a),b>>=1)if(b&1)Mul(ans,a);return ans;}
}using namespace modular;

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<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

struct basis
{
	int v[5];
	basis(){v[0]=v[1]=v[2]=v[3]=v[4]=0;}
	bool insert(int x)
	{
		for(int i=4;i>=0;i--)
			if(((x>>i)&1)&&v[i]) x^=v[i];
		if(!x) return 0;
		for(int i=4;i>=0;i--)
		{
			if((x>>i)&1)
			{
				v[i]=x;
				for(int j=4;j>i;j--)
					if((v[j]>>i)&1) v[j]^=v[i];
				break;
			}
		}
		return 1;
	}
	int hash()
	{
		int res=0;
		for(int i=4;i>=0;i--)
			res=(res<<(i+1))|v[i];
		return res;
	}
}b[400];

int idx,id[(1<<15)+10],empid,single[32];
int mer[400][400];

void dfs(basis now)
{
	int v=now.hash();
	if(id[v]) return;
	id[v]=++idx,b[idx]=now;
	for(int i=1;i<=31;i++)
	{
		basis tmp=now;
		if(tmp.insert(i)) dfs(tmp);
	}
}

void init()
{
	dfs(basis());
	for(int i=1;i<=idx;i++)
	{
		for(int j=i;j<=idx;j++)
		{
			bool ins=1;
			basis now=b[i];
			for(int k=4;k>=0;k--)
			{
				if(!b[j].v[k]) continue;
				if(!now.insert(b[j].v[k])){ins=0;break;}
			}
			mer[i][j]=mer[j][i]=(ins?id[now.hash()]:0);
		}
	}
	empid=id[basis().hash()];
	for(int i=1;i<32;i++)
	{
		basis now; now.insert(i);
		single[i]=id[now.hash()];
	}
}

int n,m;
int cnt,head[N],nxt[N<<1],to[N<<1],w[N<<1];
int rt,c3,bid,dis[N],dep[N];
int f[2][400];
bool vis[N];

void adde(int u,int v,int wi)
{
	to[++cnt]=v;
	w[cnt]=wi;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa)
{
	vis[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==1)
		{
			if(u!=rt) c3=dis[u]^w[i];
			continue;
		}
		if(vis[v])
		{
			if(v!=fa&&dep[v]<dep[u])
				bid=mer[bid][single[w[i]^dis[u]^dis[v]]];
			continue;
		}
		dep[v]=dep[u]+1,dis[v]=dis[u]^w[i],dfs(v,u);
	}
}

int main()
{
	init();
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		adde(u,v,w),adde(v,u,w);
	}
	bool pre=0,now=1;
	f[now][empid]=1;
	for(int i=head[1];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v]) continue;
		rt=v,c3=-1,bid=empid,dfs(v,0);
		if(c3!=-1) c3^=w[i];
		swap(pre,now);
		memset(f[now],0,sizeof(f[now]));
		for(int j=1;j<=idx;j++)
		{
			Add(f[now][j],f[pre][j]);
			Add(f[now][mer[j][bid]],f[pre][j]);
			if(c3!=-1)
			{
				Add(f[now][mer[j][bid]],f[pre][j]);
				Add(f[now][mer[j][mer[bid][single[c3]]]],f[pre][j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=idx;i++) Add(ans,f[now][i]);
	printf("%dn",ans);
	return 0;
}
/*
7 9
1 2 3
2 3 2
3 1 2
1 4 1
1 5 1
4 5 2
1 6 3
6 7 3
7 1 1
*/
程序员灯塔
转载请注明原文链接:【CF1299D】Around the World(线性基)
喜欢 (0)