题目链接：1039C - Network Safety/1040E - Network Safety
题目大意：不得不说这场比赛的题面真的是又臭又长......
有n个点，m条边，每个点有对应的权值c[i]，权值的范围是([0,2^{k}-1])。称一条边为安全的，当且仅当边两端的点权不同，题目保证初始状态下的所有边都是安全的。现在问你有多少个pair<set<int> A,int x>（找不到更好的语言来描述了），使得当所有A中的点的权值都变为c[i] xor x时，仍然保证所有m条边都是安全的。
题解：显然当没有其他限制时，对任意的x，set<int>A的个数都为(2^{n})，考虑一条边{u,v}，若x=c[u] xor c[v]，则u和v会被绑定，即这两个点要么都在A内，要么都不在A内。这样对任意的x，我们就能用并查集求出连通块的个数（在被绑定的两个点之间连边），此时设连通块个数为sz，则对于这个x，对应的set<int>A的个数就有(2^{sz})个。显然对应set<int>A的个数不为(2^{n})的x不会超过m个，我们只需对所有相同的m进行分开求解。这样最终的答案就是(sum_{i=1}^{cnt} 2^{sz_i}+(2^{k}-cnt)cdot 2^{n})。
注意若直接用平常的方法对fa数组进行初始化的话时间复杂度会变为O(nm)，会导致TLE。因此在处理每一个x时，要记录下被修改的点，还原时只需还原这些点对应的值就好了。
#include<bits/stdc++.h> using namespace std; #define N 500001 #define LL long long #define MOD 1000000007 set<LL>s; struct rua{LL x,u,v;}a[N]; LL n,m,k,c[N],fa[N],sz,cnt,ans; bool cmp(rua x,rua y){return x.x<y.x;} LL Find(LL x){return fa[x]==x?x:fa[x]=Find(fa[x]);} LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;} void add(LL u,LL v) { s.insert(u),s.insert(v); if(Find(u)!=Find(v))fa[Find(u)]=Find(v),sz--; } int main() { scanf("%I64d%I64d%I64d",&n,&m,&k); for(LL i=1;i<=n;i++) scanf("%I64d",&c[i]),fa[i]=i; for(LL i=1;i<=m;i++) scanf("%I64d%I64d",&a[i].u,&a[i].v), a[i].x=c[a[i].u]^c[a[i].v]; sort(a+1,a+m+1,cmp); for(LL i=1;i<=m;) { LL j=i;sz=n; for(auto x:s)fa[x]=x;s.clear(); while(j<=m && a[j].x==a[i].x) add(a[j].u,a[j].v),j++; i=j,cnt++,ans+=qow(2,sz),ans%=MOD; } return printf("%I64d ",(ans+(qow(2,k)+MOD-cnt)*qow(2,n)%MOD)%MOD),0; }