G. Xor-matic Number of the Graph

http://codeforces.com/problemset/problem/724/G

题意：给你一张无向图。定义一个无序三元组(u,v,s)表示u到v的(不一定为简单路径)路径上xor值为s。求出这张无向图所有不重复三元组的s之和。1≤n≤10^5,1≤m≤2*10^5。

想法：

如果做过【Wc2011 xor】这道题目(题解)，那么问题变得简单起来了。

①假设我们钦定一个(u,v),设任意一条u->v的路径xor值为X,该连通图所有小环xor值构成的序列为{Ai}。

那么(u,v)的所有路径的xor值可以由X xor {Ai}的子集xor值得到。于是一个(u,v)的 s 之和变成了求X xor{Ai}的子集可以得到多少个不同的数，这些不同的数的和是多少？

如果能知道{Ai}的子集xor值的值域，那么好办了。于是用线性基得到值域{T}。求和的话，按位考虑定义S(i)为{T}中第i为1的个数，为0的个数取个补集就好了。

对于一个(u,v)：

②考虑所有的无序点对(u,v)的答案。上面说过任意一条u->v的路径都可以，不如就钦定是DFS遍历得到DFS树的树上路径。

树上两点路径xor值的求法很简单：设dis(i)表示第i个到根节点路径xor值。

dis(a,b)=dis(a) xor dis(lca(a,b)) xor dis(b) xor dis(lca(a,b))=dia(a) xor dis(b)。

根据上面求ans 的式子，ans只与X的第j位是什么有关，所以设cnt(i)表示两点路径xor值第i位为1的个数。cnt(i)可以利用上面dis(a,b)=dia(a) xor dis(b)求。

对于所有(u,v):

于是解决了。

#include<cstdio>

#include<vector>

#define ll long long

const int len(),MP();

struct Node{int nd;ll co;};

std::vector<Node>Edge[len+];

int n,m,u,v,top,ans,much,vis[len+];

ll sum,S[],cnt[],now[];//cnt(i) 统计 i-th =0的个数 now(i):dx^dy i-th==1的个数

ll st[len+],dis[len+],All,t;

struct Base_Linear

{

    ll p[];int size;

    void ins(ll x)

    {

        for(int j=;j>=;j--)

        if((x>>j)&)

        {

            if(p[j])x^=p[j];

            else {p[j]=x;size++;break;}

        }

    }

}BL;

template <class T>void read(T &x)

{

    x=;int f=;char ch=getchar();

    while(ch<''||ch>''){f=(ch=='-');ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    x=f?-x:x;

}

ll power(int a,int b)

{

    ll t=,y=a;

    for(;b;b>>=)

    {

        if(b&)t=(t*y)%MP;

        y=(y*y)%MP;

    }

    return t;

}

void add(int a,int b,ll c){Edge[a].push_back((Node){b,c});}

void plus(ll x)

{

    for(int j=;j<=;j++)

    if(((x>>j)&)==)cnt[j]++;

}

void Dfs(int x)

{

    much++; vis[x]=; plus(dis[x]); st[++top]=dis[x];

    for(int v=,sz=Edge[x].size();v<sz;v++)

    {

        Node y=Edge[x][v];

        if(vis[y.nd])BL.ins(dis[x]^dis[y.nd]^y.co);

        else

        {

            dis[y.nd]=dis[x]^y.co;

            Dfs(y.nd);

        }

    }

}

void Back()

{

    for(int j=;j<=;j++)cnt[j]=now[j]=S[j]=;

    for(int j=;j<=;j++)BL.p[j]=; BL.size=;

    much=; All=;

}

void Total()

{

    for(;top;top--)

    {

        for(int j=;st[top];j++,st[top]>>=)

        if(st[top]&)now[j]=(now[j]+cnt[j])%MP;

    }

    for(int j=;j<=;j++)All|=BL.p[j];

    for(int j=;All;j++,All>>=)

    if(All&)S[j]=power(,BL.size-);

    All=power(,BL.size); ll C=;

    for(int j=;j<=;j++,C<<=,C%=MP)

    {

        sum=(ll)much*(much-)/;

        ll t1=now[j]*(All-S[j])%MP;

        ll t2=((sum-now[j])*S[j])%MP;

        ans=(ans+C*t1+C*t2)%MP;

    }

}

int main()

{

    read(n),read(m);

    for(int i=;i<=m;i++)

    {

        read(u),read(v),read(t);

        add(u,v,t),add(v,u,t);

    }

    for(int i=;i<=n;i++)

    if(!vis[i])//图可能不连通

    {

        Back();

        Dfs(i);

        Total();

    }

    ans+=ans<?MP:;

    printf("%d",ans);

    return ;

}

巴特西

Codeforces 724 G Xor-matic Number of the Graph 线性基+DFS

G. Xor-matic Number of the Graph

最新文章

热门文章