zcmimi's blog
avatar
zc
2020-06-04 07:29:00
  • 本文总阅读量
查看原题

点击跳转

做这题之前可以看看[WC201]最大XOR和路径

可以考虑换个思路:

对于每一对点的每一位,有多少种方案能使该位的xor和为1

dfs求出1到各点x的任意一条简单路径xord_x,那么求xy的简单路径长度就是d_x ~ xor ~ d_y

dfs的过程中也可以顺便求出所有环的xor和,这些可以用来增广简单路径,我们将这些环的xor和插入到线性基中

若线性基中有cnt个非零位,则一共会产生2^{cnt}个不同的xor

到了这一步,通过枚举两个点来统计路径的复杂度仍然是O(n^2 \cdot 60)的,我们要采用更高效的方法

直接讨论d_x对答案的贡献

先统计出第k位为0的数的个数,我们将其记为x,再统计出第k位为1的数的个数,记为y,总共有point个点

  1. d_x的第k位为1,线性基中有第k位为1的数: 此时我们有两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总体对于答案的贡献为:2^k\cdot 2^{cnt-1}\cdot (point-1),减1就是为了把自己给去掉。
  2. d_i的第k位为1,线性基中没有第k位为1的数: 这个时候另一个点只能取第k位为0的,, 所以总贡献为: 2^k\cdot 2^{cnt}\cdot x

  3. d_i的第k位为0,线性基中有第k位为1的数: 一样的,, 两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总贡献为: 2^k\cdot2^{cnt-1}\cdot(point-1)
  4. d_i的第k位为0,线性基中没有第k位为1的数: 另一个点只能取第k位为1的,总贡献: 2^k\cdot 2^{cnt}\cdot y


#include<bits/stdc++.h>
typedef long long ll;
const int N=100001;
const ll P=1000000007,inv=500000004;
struct edge{int to,nxt;ll w;}e[N<<2];
int n,m,cnt=1,head[N],tt;
ll pw[61],p[61],a[N],d[N];
bool v[N],u[N<<2];
void add(int x,int y,ll w){e[++cnt].to=y,e[cnt].nxt=head[x],head[x]=cnt,e[cnt].w=w;}
void ins(ll x){
    for(int i=60;x,~i;--i)if(x>>i){
        if(!p[i]){p[i]=x;return;}
        x^=p[i];
    }
}
void dfs(int x){
    a[++tt]=d[x],v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!v[to])d[to]=d[x]^e[i].w,dfs(to);
        else if(!u[i^1])ins(d[x]^d[to]^e[i].w),u[i^1]=1;
}
ll calc(){
    ll ans=0;int x,y,tot=0;bool ff;
    for(int i=0;i<=60;++i)tot+=p[i]>0;
    for(int j=0;j<=60;++j){
        x=y=ff=0;
        for(int i=1;i<=tt;++i)
            (a[i]>>j&1)?++x:++y;
        for(int i=0;i<=60;++i)
            if(p[i]>>j&1){ff=1;break;}
        for(int i=1;i<=tt;++i,ans%=P)
            if(a[i]>>j&1)
                if(ff)ans+=pw[tot-1]*(tt-1)%P*pw[j]%P;
                else ans+=pw[tot]*y%P*pw[j]%P;
            else
                if(ff)ans+=pw[tot-1]*(tt-1)%P*pw[j]%P;
                else ans+=pw[tot]*x%P*pw[j]%P;
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y;ll w,ans=0;
    while(m--)
        scanf("%d%d%lld",&x,&y,&w),
        add(x,y,w),add(y,x,w);
    pw[0]=1;
    for(int i=1;i<=60;++i)pw[i]=(pw[i-1]<<1)%P;
    for(int i=1;i<=n;++i)if(!v[i]){
        memset(p,0,sizeof p);
        tt=0,dfs(i);
        (ans+=calc())%=P;
    }
    ans=ans*inv%P;
    printf("%lld\n",ans);
}
LG CF724G Xor-matic Number of the Graph
comment评论
Search
search