Codeforces 724G - Xor-matic Number of the Graph（线性基）

一道还算不套路的线性基罢……

首先由于图不连通，并且不同连通块之间的点显然不可能产生贡献，因此考虑对每个连通块单独计算贡献。按照 P4151 的套路可以对每个连通块先找出它的一棵生成树，记 \(d_u\) 为 \(u\) 到生成树树根上所有边权值的异或和。对于生成树上所有非树边 \((u,v,w)\)，\(u\to v\) 在树上的路径与这条边本身显然会形成一个环，且环的权值为 \(d_u\oplus d_v\oplus w\)，我们将这个环插入线性基。那么对于该联通块中的两点 \(u,v\)，所有 \(u\to v\) 路径本质不同的异或和都可以写成 \(d_u\oplus d_v\oplus x\) 的形式，其中 \(x\) 可以表示为线性基中向量的线性组合。

显然暴力枚举 \(u,v\) 是不可行的，考虑换个方式计算贡献，对于每一个二进制位 \(2^p\)，我们计算有多少个 \(u,v,S\) 满足 \(d_u\oplus d_v\oplus\operatorname{xor}\limits_{x\in S}x\) 的 \(2^p\) 位为 \(1\)，那么会产生 \(2^p\times\text{满足条件的三元组}(u,v,S)\text{的个数}\) 的贡献。那么这个贡献怎么计算呢？分两种情况，设线性基为 \(b_1,b_2,\cdots,b_m\)，那么：

如果 \(\exist i\) 满足 \(b_i\) 的 \(2^p\) 位为 \(1\)，那么不论剩下 \(m-1\) 个数选不选，我们总可以控制 \(b_i\) 的选/不选来实现 \(2^p\) 的第 \(i\) 位为 \(1\)，因此可以表示为 \(\operatorname{xor}\limits_{x\in S}x\) 的形式，并且 \(2^p\) 位为 \(1\) 的数的个数为 \(2^{p-1}\)。而根据线性基的性质，对于所有可以表示 \(\operatorname{xor}\limits_{x\in S}x\) 的形式的 \(y\)，都恰好存在 \(2^{t-m}\) 个集合 \(S\) 满足 \(\operatorname{xor}\limits_{x\in S}x=y\)，其中 \(t\) 为非树边个数。也就是说不论 \(u,v\) 是什么，总有 \(2^{t-1}\) 个集合 \(S\) 满足 \(d_u\oplus d_v\oplus\operatorname{xor}\limits_{x\in S}x\) 的 \(2^p\) 位为 \(1\)，因此符合条件的 \(u,v,S\) 的个数为 \(2^{t-1}\times\dbinom{n}{2}\)。
否则不论 \(S\) 是什么，都有 \(\operatorname{xor}\limits_{x\in S}x\) 的 \(2^p\) 位为 \(0\)，故 \((u,v,S)\) 符合条件当且仅当 \(d_u,d_v\) 的 \(2^p\) 位的值不同，开个桶统计下有多少个 \(u\) 满足 \(d_u\) 的 \(2^p\) 位为 \(0\)，贡献即为 \(2^t\times d_p\times(siz-d_p)\)，其中 \(siz\) 为连通块大小。

剩下的就是乱搞搞的事了，时间复杂度 \(n\log^2v\)，其中 \(v\) 为值域大小。

const int MAXN=1e5;

const int MAXM=2e5;

const int MAXB=60;

const int MOD=1e9+7;

const int INV2=5e8+4;

int n,m,cnt=0,num[MAXB+5];ll a[MAXB+5];

int hd[MAXN+5],to[MAXM*2+5],nxt[MAXM*2+5],ec=0;ll val[MAXM*2+5];

void adde(int u,int v,ll w){to[++ec]=v;val[ec]=w;nxt[ec]=hd[u];hd[u]=ec;}

void init(){memset(a,0,sizeof(a));cnt=0;}

void ins(ll x){

	for(int i=MAXB;~i;i--) if(x>>i&1){

		if(!a[i]){++cnt;a[i]=x;return;}

		else x^=a[i];

	}

}

bitset<MAXN+5> vis;

ll dis[MAXN+5];vector<int> v;

void dfs(int x,ll cur){

	dis[x]=cur;vis[x]=1;v.pb(x);

	for(int e=hd[x];e;e=nxt[e]){

		int y=to[e];ll z=val[e];

		if(!vis[y]) dfs(y,cur^z);

		else ins(dis[x]^dis[y]^z);

	}

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);

		adde(u,v,w);adde(v,u,w);

	}

	int ans=0;

	for(int i=1;i<=n;i++) if(!vis[i]){

		init();memset(num,0,sizeof(num));v.clear();dfs(i,0);

		for(int j=0;j<=MAXB;j++) for(int u:v)

			if(dis[u]>>j&1) num[j]++;

		for(int j=0;j<=MAXB;j++){

			bool flg=0;

			for(int k=0;k<=MAXB;k++) if(a[k]>>j&1) flg=1;

			if(flg) ans=(ans+(1ll<<j)%MOD*((1ll<<cnt-1)%MOD)%MOD*v.size()%MOD*(v.size()-1)%MOD*INV2)%MOD;

			else ans=(ans+(1ll<<j)%MOD*((1ll<<cnt)%MOD)%MOD*num[j]%MOD*(v.size()-num[j]))%MOD;

		}

	} printf("%d\n",ans);

	return 0;

}

巴特西

Codeforces 724G - Xor-matic Number of the Graph（线性基）

最新文章

热门文章