目录
题目链接题解代码
题目链接
CF1039C.Network Safety
题解
对于一对相邻点，^异或后相同的值唯一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;
}
转载于:https://www.cnblogs.com/sssy/p/9678729.html
