bzoj3871: [Neerc2013 C]Cactus Automorphisms || 3899: 仙人掌树的同构

时间：2021-10-11 08:01:41

Description

给定一个N，N<=50 000个节点的仙人掌，其是指每条边最多在一个环中的无向图，求仙人掌有多少种自同构。自同构是指得是图的顶点集合V到V的变换M，

bzoj3871: [Neerc2013 C]Cactus Automorphisms || 3899: 仙人掌树的同构

以P1^a1*P2^a2...Pk^ak的形式输出，其中Pk是素数。

建圆方树，找到重心，如果重心有两个就在它们之间的边上插一个点，同构变换后重心不变

以重心为根得到有根树，对于树点，统计交换子树造成的同构，将所有贡献累乘得到答案，对于环点，如果不是重心，就只有翻转这个环能产生新的同构，否则这个环除了翻转还可以旋转，用hash处理这些情况。注意处理环的时候需要把环点的相邻点排成原来在仙人掌上的顺序。

#include<cstdio>

#include<algorithm>

typedef unsigned long long u64;

const int N=;

int n,m,fac[N];

int es[N],enx[N],e0[N],e1[N],ep=;

bool _c[N];

void ae(int*e,int a,int b){

    es[ep]=b;enx[ep]=e[a];e[a]=ep++;

    es[ep]=a;enx[ep]=e[b];e[b]=ep++;

}

void de(int*e,int a,int b){

    for(int*i=e+a;*i;i=enx+*i){

        int u=es[*i];

        if(u==b){

            *i=enx[*i];

            return;

        }

    }

}

int dfn[N],low[N],tk=,ss[N],sp=,n1;

void tj(int w,int pa){

    dfn[w]=low[w]=++tk;

    ss[++sp]=w;

    for(int i=e0[w];i;i=enx[i]){

        int u=es[i];

        if(!u)continue;

        if(!dfn[u]){

            es[i^]=;

            tj(u,w);

            es[i^]=w;

            if(ss[sp]==u)--sp,ae(e1,w,u);

        }else if(dfn[u]<dfn[w]){

            int rp=;

            ae(e1,u,++n1);

            _c[n1]=;

            while(sp&&dfn[ss[sp]]>dfn[u])ae(e1,ss[sp--],n1);

        }

    }

}

int sz[N],cg[],cgp=,rt;

void f1(int w,int pa){

    bool is=;

    sz[w]=;

    for(int i=e1[w];i;i=enx[i]){

        int u=es[i];

        if(u==pa)continue;

        f1(u,w);

        sz[w]+=sz[u];

        if(sz[u]*>n1)is=;

    }

    if(sz[w]*<n1)is=;

    if(is)cg[cgp++]=w;

}

u64 h[N],h1[N],h2[N];

int cs[N],cp;

bool cmp_h(int a,int b){return h[a]<h[b];}

int a1[N],a2[N],mx=;

u64 a3[N];

void mul(int x){

    ++a1[x];

    if(x>mx)mx=x;

}

void mulfac(int x){

    ++a2[x];

    if(x>mx)mx=x;

}

void f2(int w,int pa){

    for(int i=e1[w];i;i=enx[i]){

        int u=es[i];

        if(u!=pa)f2(u,w);

    }

    cp=;

    for(int i=e1[w],d=;i;i=enx[i]){

        int u=es[i];

        if(u==pa){

            d=;

            continue;

        }

        if(d)cs[cp++]=u;

    }

    for(int i=e1[w];i;i=enx[i]){

        int u=es[i];

        if(u==pa)break;

        cs[cp++]=u;

    }

    if(_c[w]){

        if(w==rt){

            u64 p0=,pp=;

            for(int i=;i<=cp;++i){

                h1[i]=h1[i+cp]=h2[i]=h2[i+cp]=h[cs[i-]];

                pp*=p0;

            }

            for(int i=;i<=cp*;++i)h1[i]+=h1[i-]*p0;

            for(int i=cp*;i;--i)h2[i]+=h2[i+]*p0;

            int c=;

            for(int i=cp;i<cp*;++i)c+=(h1[i]-h1[i-cp]*pp==h1[cp]);

            for(int i=cp;i;--i)c+=(h2[i]-h2[i+cp]*pp==h1[cp]);

            mul(c);

        }else{

            u64 h1=,h2=;

            for(int i=;i<cp;++i)h1=h1*+h[cs[i]];

            for(int i=cp-;i>=;--i)h2=h2*+h[cs[i]];

            if(h1==h2)mul();

            h[w]=std::min(h1,h2);

            h[w]^=h[w]>>^h[w]*<<^41546541735416351llu;

        }

    }else{

        std::sort(cs,cs+cp,cmp_h);

        h[w]=;

        for(int i=,j=;i<cp;i=j){

            for(;j<cp&&h[cs[i]]==h[cs[j]];++j);

            mulfac(j-i);

        }

        for(int i=;i<cp;++i)h[w]=h[w]*+h[cs[i]];

        h[w]^=h[w]>>^h[w]*<<^12218653252112541llu;

    }

}

int _(){

    int x=,c=getchar();

    while(c<)c=getchar();

    while(c>)x=x*+c-,c=getchar();

    return x;

}

int ps[N],pp,mp[N],ed[N];

bool np[N];

int main(){

    n=_();m=_();

    n1=n;

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

        pp=_();

        for(int j=;j<pp;++j)ps[j]=_();

        for(int j=;j<pp-;++j)ae(e0,ps[j],ps[j+]);

    }

    for(int w=;w<=n;++w){

        for(int i=e0[w];i;i=enx[i]){

            int u=es[i];

            if(ed[u]!=w)ed[u]=w;

            else if(u>w)--a1[];

        }

    }

    tj(,);

    f1(,);

    if(cgp==){

        if(_c[cg[]])rt=cg[];

        else if(_c[cg[]])rt=cg[];

        else{

            rt=++n1;

            ae(e1,n1,cg[]);

            ae(e1,n1,cg[]);

            de(e1,cg[],cg[]);

            de(e1,cg[],cg[]);

        }

    }else rt=cg[];

    f1(rt,);

    f2(rt,);

    for(int i=mx;i;--i)a2[i]+=a2[i+];

    for(int i=mx;i;--i)a2[i]+=a1[i];

    pp=;

    for(int i=;i<=mx;++i){

        if(!np[i])ps[pp++]=mp[i]=i;

        for(int j=;j<pp&&i*ps[j]<=mx;++j){

            np[i*ps[j]]=;

            mp[i*ps[j]]=ps[j];

            if(i%ps[j]==)break;

        }

    }

    for(int i=;i<=mx;++i){

        for(int x=i;x>;x/=mp[x])a3[mp[x]]+=a2[i];

    }

    pp=;

    for(int i=;i<=mx;++i)if(a3[i])ps[pp++]=i;

    printf("%d\n",pp);

    for(int j=;j<pp;++j)printf("%d %lld\n",ps[j],a3[ps[j]]);

    return ;

}

相关文章