题目概述

有 $n$ 个点 $m$ 条边，每个点的点权是 $a_i(0\le a_i\le 2^{K}-1)$ ，现在要把一个点集 $A$ 的点权异或上 $x$ ，问有多少种 $(A,x)$ 满足不存在一条边 $(u,v)$ 满足 $a_u=a_v$ 。

解题报告

翰爷秒了，补集转化大法好。一条边满足条件需要 $a_u\ xor\ a_v\not=x$ ，所以一个点集 $A$ 的贡献是连出去的边中没有出现的权值的个数，也就是：

$$ \sum_{A}2^{K}-|\{a_u\ xor\ a_v|u\in A,v\not\in A\}|\\ 2^{n}2^{K}-\sum_{A}|\{a_u\ xor\ a_v|u\in A,v\not\in A\}| $$

现在变成了求每条边的贡献。给每条边一个边权 $a_u\ xor\ a_v$ ，然后我们需要把边权相同的边一起考虑，那么现在就要至少有一条边满足一个点在点集中另一个不在，发现这不是很好求，所以我们可以补集转化，那么这些边形成了很多连通块，你会发现每个连通块里面只有两种情况就是全取和全不取，所以就很简单了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=500000,maxm=500000,MOD=1e9+7;

int n,m,K,ans,x[maxm+5],y[maxm+5],ID[maxm+5],pw[maxm+5];
LL a[maxn+5],w[maxm+5];int ti,vis[maxn+5],fat[maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline bool cmp(const int &A,const int &B) {return w[A]<w[B];}
#define fat(x) (vis[x]<ti?(vis[x]=ti,fat[x]=x):fat[x])
int getfa(int x) {if (x==fat(x)) return x;return fat[x]=getfa(fat(x));}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&K);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]),w[i]=a[x[i]]^a[y[i]],ID[i]=i;
    sort(ID+1,ID+1+m,cmp);pw[0]=1;for (int i=1;i<=m;i++) pw[i]=((LL)pw[i-1]<<1)%MOD;
    ans=1;for (int i=1;i<=n+K;i++) ans=((LL)ans<<1)%MOD;
    for (int i=1,j;i<=m;i=j){
        for (j=i;j<=m&&w[ID[i]]==w[ID[j]];j++);int sum=0,num=0;ti++;
        for (int t=i,k=ID[t];t<j;k=ID[++t]){
            if (vis[x[k]]<ti) sum++,num++;if (vis[y[k]]<ti) sum++,num++;
            int fx=getfa(x[k]),fy=getfa(y[k]);if (fx!=fy) fat[fx]=fy,num--;
        }AMOD(ans,MOD-(LL)pw[n-sum]*(pw[sum]-pw[num]+MOD)%MOD);
    }return printf("%d\n",ans),0;
}