codeforces724G Xor-matic Number of the Graph

时间：2022-07-28 07:03:22

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

题目链接：codeforces724G

正解：线性基
解题报告：

　　一道线性基好题…

　　是不是感觉和$WC2011$的那道题有相通之处呢？首先搞出一棵$dfs$树，并且得到树上每个环的$xor$值。

　　我们发现，两点间就是本来的$dis$ $xor$ 某些环的$xor$值，即可组合得到一些新的异或值。位运算的题目，我们显然按位来做。

　　首先，对于两个这一位同时为$1$或者同时为$0$的，我们考虑若要有贡献，必须是从环上得到一个这一位为$1$的$xor$值，如果线性基这一位都是$0$则无贡献，否则我们可以考虑，假设线性基中有$r$个向量，那么我们把这一位为$1$的一个向量排除在外，剩下的随便选，任意组合，也就是$2^{r-1}$，得到一个权值，再根据得到的权值这一位是$1$还是$0$，来决定被排除在外的这个向量选不选，所以贡献就是$2^{r-1}$。

　　同理，如果一个是$1$一个是$0$，那么我同样是分类讨论，向量中有无这一位是$1$的，分别算贡献即可。

//It is made by ljh2000

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <string>

#include <complex>

using namespace std;

typedef long long LL;

typedef long double LB;

typedef complex<double> C;

const double pi = acos(-1);

const int mod = 1000000007;

const int MAXN = 200011;

const int MAXM = 400011;

int n,m,ecnt,first[MAXN],to[MAXM],next[MAXM],scnt,dui[MAXN],cir_cnt,r;

LL dis[MAXN],w[MAXM],p[70]/*!!!不要开大了...*/,cir[MAXM],ans,fp[MAXM<<1],cnt[2];//数组不要开小了!!!

bool vis[MAXN],in[MAXN];

inline void link(int x,int y,LL z){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z; }

inline LL fast_pow(LL x,LL y){ LL r=1; while(y>0) { if(y&1) r*=x,r%=mod; x*=x; x%=mod; y>>=1; } return r; }

inline int getint(){

    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline LL getlong(){

    LL w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void dfs(int x,LL dd,int fa){

	if(dis[x]==-1) dis[x]=dd;

	else {//找环

		cir[++cir_cnt]=dd^dis[x];

		return ;

	}

	vis[x]=1; dis[x]=dd; dui[++scnt]=x;

	for(int i=first[x];i;i=next[i]) {

		int v=to[i]; if(v==fa) continue;

		dfs(v,dd^w[i],x);

	}

}

inline void build(){//构线性基

	memset(p,0,sizeof(p)); r=0;

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

		for(int j=62;j>=0;j--) {

			if(!(cir[i]>>j)) continue;

			if(!p[j]) { p[j]=cir[i]; break; }

			cir[i]^=p[j];

		}

	}

	for(int j=0;j<=62;j++) if(p[j]!=0) r++;//计算线性基有效的向量个数

}

inline LL calc(){

	build(); LL tot=0,now; bool flag;

	for(int i=0;i<=62;i++) {//按位算贡献

		cnt[0]=cnt[1]=0; flag=false;//是否存在某个向量的这一位为1

		for(int j=0;j<=62;j++) if((p[j]>>i)&1) { flag=true; break; }

		for(int j=1;j<=scnt;j++) cnt[(dis[ dui[j] ]>>i)&1]++;//统计每个dis的这一位是0还是1

		now=cnt[0]*(cnt[0]-1)/2+cnt[1]*(cnt[1]-1)/2;//组合的方式记得考虑/2!!!

		now%=mod;

		if(flag) {

			if(r>=1) now*=fp[r-1],now%=mod;

			now*=fp[i],now%=mod;

			tot+=now; tot%=mod;

		}

		now=cnt[0]*cnt[1]; now%=mod;

		if(flag) { if(r>=1) now*=fp[r-1],now%=mod; }

		else now*=fp[r],now%=mod;

		now*=fp[i],now%=mod;

		tot+=now; tot%=mod;

	}

	return tot;

}

inline void work(){

	n=getint(); m=getint(); int x,y,lim=max(n,m)*2; LL z;

	for(int i=1;i<=m;i++) { x=getint(); y=getint(); z=getlong(); link(x,y,z); link(y,x,z); }

	fp[0]=1; for(int i=1;i<=lim;i++) fp[i]=fp[i-1]*2,fp[i]%=mod;//预处理2的整数幂

	memset(dis,-1,sizeof(dis));

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

		if(vis[i]) continue;

		scnt=0; cir_cnt=0;

		dfs(i,0,0);

		ans+=calc();

		ans%=mod;

	}

	printf("%I64d",ans);

}

int main()

{

    work();

    return 0;

}

　　

相关文章