题目
思路
考虑如果不安全则一定满足式子\(a\oplus x=b\),移项之后直接\(a\oplus b=x\)
也就是指a和b的状态一定是一样的,即要么都异或,要么都不异或,对其进行冰茶姬的合并
对于同一个x,方案数直接是\(2^{cnt}\),cnt表示冰茶姬数量
对于其他的,即没有点权异或起来为x的x,也是很好算的,直接剩余x的数量乘上\(2^n\)
代码
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int mod=1e9+7;
namespace IO
{
void read(int &x)
{
x=0;
int f=1;
char c=getchar();
while('0'>c||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
x*=f;
}
void read(long long &x)
{
x=0;
int f=1;
char c=getchar();
while('0'>c||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
x*=f;
}
void write(int x)
{
if(x<10)
putchar(x%10+'0');
else
{
write(x/10);
putchar(x%10+'0');
}
}
void write(long long x)
{
if(x<10)
putchar(x%10+'0');
else
{
write(x/10);
putchar(x%10+'0');
}
}
}
namespace ufs
{
int tot;
int fa[1000005];
void makeset(int n)
{
tot=n;
for(int i=1;i<=n;i++)
fa[i]=i;
}
int findset(int x)
{
if(x==fa[x])
return x;
return fa[x]=findset(fa[x]);
}
void merge(int u,int v)
{
int a=findset(u);
int b=findset(v);
if(a==b)
return;
tot--;
fa[a]=b;
}
}
using namespace IO;
using namespace ufs;
struct edge
{
int u,v;
};
int n,m;
int cnt;
long long limit,ans;
long long c[500005];
map<long long,int> hashh;
vector<int> g[500005];
vector<edge> w[500005];
long long qkpow(int a,long long b)
{
if(b==0)
return 1;
if(b==1)
return a;
long long t=qkpow(a,b/2);
t=t*t%mod;
if(b%2==1)
t=t*a%mod;
return t;
}
int main()
{
read(n);
read(m);
read(limit);
makeset(n);
limit=qkpow(2,limit);
for(int i=1;i<=n;i++)
read(c[i]);
for(int i=1,u,v;i<=m;i++)
{
read(u);
read(v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
for(int j=0;j<g[i].size();j++)
if(hashh.count(c[i]^c[g[i][j]])==0)
hashh[c[i]^c[g[i][j]]]=++cnt;
for(int i=1;i<=n;i++)
for(int j=0;j<g[i].size();j++)
w[hashh[c[i]^c[g[i][j]]]].push_back((edge){i,g[i][j]});
limit-=cnt;
for(int i=1;i<=cnt;i++)
{
for(int j=0;j<w[i].size();j++)
merge(w[i][j].u,w[i][j].v);
ans=(ans+qkpow(2,tot))%mod;
for(int j=0;j<w[i].size();j++)
{
fa[w[i][j].u]=w[i][j].u;
fa[w[i][j].v]=w[i][j].v;
}
tot=n;
}
ans=(ans+limit*qkpow(2,n)%mod)%mod;
write(ans);
return 0;
}