codeforces 724G. Xor-matic Number of the Graph

Posted on | In ,

题目链接

给一个无向图，含边权，并定义这样一种三元组(u, v, t)满足：从u到v有一条路径且路径上的边权异或和为t。求所有三元组的t的和

  1. 我们对它逐步拆解分析，先考虑最简单的情况——如果这个图是一棵树。首先我们发现由于异或的特殊性，经过相同的边两次等价于没有经过，所以对于所有的点对(u, v)它有唯一的异或和dis(u, v) 且等于dis(u, root) ^ dis(v, root)，因为路径上重合的部分被异或掉了。这样的关系给了我们一个启示：可以一次计算出所有点到根的异或和（用dfs）。然后再用它来求两点间的异或和。

  2. 接下来我们向图中加入环，我们知道如果在一条边上“往返”，是对结果无影响的，所以对于该图中所有的环（重边也算），都可以随意地向(u, v)的基本路径中添加。相当于存在这样一个集合B，集合中是每个环完整一圈的异或和，我们可以从这个集合中任意取数并异或上1中的结果。

    因此我们可以去计算集合B的线性基。

  3. 进而我们需要考虑的是如何计算，由于点和边的数量级是1e5，如果遍历点对会超时，这个时候就需要找规律。最终是求和，我们按照二进制位去累加各种情况的贡献，对于第i位，去计数有多少点的深度值dep[i] = dis(i, root)在这一位上是1或0，分别是tot0和tot1，如果不考虑环，贡献值为tot0tot1\2^i。即最终有tot0*tot1对点的距离值的第i位是1，那就把它们加在一起。考虑环的话则，如果该位原本没有1，可以通过B的线性基来补充。具体公式在代码中。这样计算的复杂度是O(62*m)。

  4. 对于多个联通块，每发现一个联通块就单独计算它的贡献并累加。需即使清除记录的上个联通块的环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;

//https://codeforces.com/contest/724/problem/G

const int maxn=1e5+4;
const int maxm=4e5+4;
const int maxp=62;
const int mod=1e9+7;
#define ll long long
struct edge{
    int to,next;	//to是该边指向的点，next是该边的上一条边的下标
    ll val;
    edge(){ to=0,next=-1,val=0;}
}es[maxm];
int head[maxn]; //head[i]是i点发出的最后一条边的下标
int cnt;
int n,m;
ll base[maxp];

ll p[maxp];
int r;  //线性基数量
ll circle[maxm],dep[maxn];
int cir;

inline void add(int u,int v,ll t){
    es[cnt].to=v;
    es[cnt].val=t;
    es[cnt].next=head[u];	//next指向上个head
    head[u]=cnt++;	//当前加入的边是head
}

int cover[maxn];    //记录本次dfs覆盖了哪些点
int cntc;
void dfs(int u,int fa,ll cur){
    cover[cntc++]=u;
    //cur是当前点到根的异或和
    dep[u]=cur;

    for(int i=head[u];i!=-1;i=es[i].next){
        int v=es[i].to;
        if(es[i].to==fa)
            continue;
        if(dep[es[i].to]==-1){
            dfs(v,u,cur^es[i].val);
        }else{
            //重复到达某个点，说明有环，添加它的值
            circle[cir++]=dep[u]^dep[v]^es[i].val;
        }
    }
}

inline void linearBase(){
    memset(p,0,sizeof(p));
    r=0;
    for(int i=0;i<cir;i++){
        ll x=circle[i];
        for(int j=maxp-1;j>=0;j--){
            if(x&(1ll<<j)){
                if(!p[j]){
                    p[j]=x;
                    break;
                }
                x^=p[j];
            }
            if(!x) break;
        }
    }
    for(int i=0;i<maxp;i++)
        if(p[i]) r++;
}

ll ans;
inline void solve(){
    linearBase();
    int i,j;
    ll tot[2];
    for(i=0;i<maxp;i++){
        tot[0]=0,tot[1]=0;
        for(j=0;j<cntc;j++){
            if(dep[cover[j]]&(1ll<<i)) tot[1]++;
            else tot[0]++;
        }
        ll tmp=(tot[0]*(tot[0]-1)/2%mod+tot[1]*(tot[1]-1)/2)%mod;   //路径异或值该位同为1或0的对子数量
        bool f=false;   //true：存在一个线性基该位为1
        for(j=0;j<maxp;j++){
            if(p[j]&(1ll<<i)){
                f=true; break;
            }
        }
        if(f){
            tmp=(tmp*base[r-1]%mod)*base[i]%mod;    //线性基能带来2^(r-1)个2^i值
            ans=(ans+tmp)%mod;
        }
        tmp=tot[0]*tot[1]%mod;
        if(f){
            tmp=(tmp*base[r-1]%mod);	//在该位有线性基，所以只有一半的能做贡献
        }else{
            tmp=tmp*base[r]%mod;    //此时由于线性基该位为0，所以2^r个线性基全做贡献
        }
        tmp=tmp*base[i]%mod;
        ans=(ans+tmp)%mod;
    }
}

int main(){
    cin>>n>>m;
    int u,v;
    ll t;
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;i++){
        scanf("%d%d%lld",&u,&v,&t);
        add(u,v,t);
        add(v,u,t);
    }
    base[0]=1;
    for(int i=1;i<maxp;i++) base[i]=(base[i-1]*2)%mod;
    memset(dep,-1,sizeof(dep));
    for(int i=1;i<=n;i++){
        if(dep[i]==-1){
            cntc=0; //清除上个联通块中的点
            cir=0;  //清除上个联通块中的环
            dfs(i,0,0);
            solve();
        }
    }
    cout<<ans%mod<<endl;
    return 0;
}