目录

[TOC]

题目链接

题解

对于一对相邻点，^异或后相同的值唯一a_i ^ t= b_i,a_i ^ b_i = t

对于不在t集合的直接算上

对于t集合,对于每个t分别计算联块的个数,然后加上联通块子集个数

代码

#include<map>

#include<vector>

#include<cstdio>

#include<algorithm>

#define int long long

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = gc;

	while(c < '0' || c > '9')c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f;

}

void print(int x) {

	if(x < 0) {

		pc('-');

		x = -x;

	}

	if(x >= 10) print(x / 10);

	pc(x % 10 + '0');

}

const int maxn = 1000007;

const int mod = 1e9 + 7;

#define LL long long

int n,m,k;

int a[maxn];

int p[maxn];

std::vector<int>v[maxn];

int id[maxn];

int bel[maxn];

int fa[maxn];

int find(int x) {

	if(fa[x] != x) fa[x] = find(fa[x]);

	return fa[x];

}

struct node {

	int u,v;

} e[maxn << 1];

std::map<LL,int>mp;

main() {

	int tot = 0;

	n = read(), m = read() , k = read();

	p[0] = 1;

	for(int i = 1;i <= n;++ i) p[i] = p[i - 1] * 2 % mod;

	for(int i = 1;i <= n;++ i) a[i] = read(),fa[i] = i;

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

		e[i].u = read(),e[i].v = read();

		int t = a[e[i].u] ^ a[e[i].v];

		if(!mp[t]) mp[t] = ++ tot;

		id[++ tot] = t;

		v[mp[t]].push_back(i);

	}

    int ans = 1ll * ((1ll << k) - tot) % mod * p[n] % mod;

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

		int size = n;

		for(int j = 0;j < v[i].size();++ j) {

			int E = v[i][j];

			int fx = find(e[E].u),fy = find(e[E].v);

			if(fx != fy) {

				fa[fx] = fy;

				size --;

			}

		}

		(ans += p[size]) %= mod;

		for(int j = 0;j < v[i].size();++ j) {

			int E = v[i][j];

			fa[e[E].u] = e[E].u;

			fa[e[E].v] = e[E].v;

		}

	}

	print(ans);

	pc('\n');

	return 0;

}

巴特西

CF1039C.Network Safety

目录

[TOC]

题目链接

题解

代码

最新文章

热门文章

巴特西

CF1039C.Network Safety

目录 [TOC]

题目链接

题解

代码

最新文章

热门文章

目录

[TOC]