[换轴][并查集][异或性质][连通分量] codeforces 1040E Network Safety

http://codeforces.com/contest/1040/problem/E

这个做法最重要的是原本的每一条边两端点一定不相等，所以两个点如果同时被异或结果一定仍然不相等。     然后就是考虑一个点被异或另一个点没有被异或的情况，一开始觉得会很复杂？但是实际上不是这样的，远没有想象中的复杂：  当x确定的时候，只有a⊕b==x的那些边会受到影响，这些边必须同时被选中，而剩下的，无所谓。。所以就把这些边连起来的点缩点之后就成了2^q的选择方式了。。

实现细节：①会卡并查集退化，所以必须写按秩合并   ②每次只要记录下被改动的点，然后下一次把这些点并查集复原即可，否则由于并查集的初始化时间复杂度会退化。

#include
//#include
//#include

using namespace std;

typedef long long LL;
const int maxn=5e5+5;
const int mod=1e9+7;

bool used[maxn];
LL encry[maxn];
LL edges[maxn][3];

unordered_map > mp;
vector last;
int p[maxn],rak[maxn];
int find(int x)
{
    return x==p[x]?x:find(p[x]);
}

LL pow2[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pow2[0]=1;
    for (int i=1;imod)
            pow2[i]-=mod;
    }
    int n,m,k,u,v;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>encry[i];
        p[i]=i;
    }
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v;
        edges[i][1]=u,edges[i][2]=v;
        mp[encry[u]^encry[v]].push_back(i);
    }
    int tf=mp.size();
    LL ta,ans=0;
    int cnt;
    vector tww;
    tww.push_back(1);
    vector &vec=tww;
    for (unordered_map >::iterator it=mp.begin();it!=mp.end();it++)
    {
        cnt=n;
        int len=last.size();
        for (int j=0;jsecond;
        len= vec.size();
        int x,y;
        for (int j=0;jmod)
            ans-=mod;
        if(ans<-mod)
            ans+=mod;

    }
    cout<<(pow2[k]*pow2[n]%mod-ans+mod)%mod<