[仙人掌同構 Hash] Codeforces Gym 100307 NEERC 13 C. Cactus Automorphisms

其實就是BZOJ3899的加強版

當時寫的東西真是不敢恭維

還是看Po姐的題解吧

我們把仙人掌拆成圓方樹 就可以直接用樹hash來做

先找重心 因為我寫的時候把兩個點也當做點雙 那麼所有邊都是圓方相接如果重心有兩個 去代表環的方點就好了

接下來是hash 圓點沒問題 子樹排完序hash 順帶記一下如果有相同 答案乘上出現次數的階乘

不是根的方點 也就是一個環 是有順序的 不能排序 然後看一下翻轉是不是一樣 乘個2

最後如果根是一個方點 那麼我們要考慮環的同構 環翻轉前後跑一通KMP就知道有幾種情況是循環同構的 乘上答案

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> abcd;

inline char nc(){
  static char buf[],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-;
  for (x=;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=,P=e9+;

int prime[N],num;
int q[N];
int vst[N],d[N];
inline void Pre(int n){
  for (int i=;i<=n;i++){
    if (!vst[i]) prime[++num]=i,d[i]=i;
    for (int j=;j<=num && (ll)i*prime[j]<=n;j++){
      vst[i*prime[j]]=; d[i*prime[j]]=prime[j];
      if (i%prime[j]==) break;
    }
  }
}

int _q[N];

inline void Print(int n){
  for (int i=n;i;i--){
    _q[i]+=_q[i+1];
    if (_q[i]){
      int t=i;
      while (t>)
    q[d[t]]+=_q[i],t/=d[t];
    }
  }
  int tot=;
  for (int i=;i<=n;i++) tot+=q[i]!=;
  printf("%d\n",tot);
  for (int i=;i<=n;i++)
    if (q[i])
      printf("%d %d\n",i,q[i]);
}

const ull ORI1=,ORI2=;
const ull BASE1=,BASE2=;
const ull END1=,END2=;

struct edge{
  int u,v,next;
}G[N<<];
int head[N],inum=;
#define V G[p].v
inline void add(int u,int v){
  int p=++inum; G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}

int n,m,bcc;

int size[N],minv=<<,rt;

inline void Root(int u,int fa){
  size[u]=; int maxv=;
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa)
      Root(V,u),size[u]+=size[V],maxv=max(maxv,size[V]);
  maxv=max(maxv,n+bcc-size[u]);
  if (maxv<minv || (maxv==minv && u>rt)) rt=u,minv=maxv;
}

ull lst[N]; int pnt;
ull H[N];

int nxt[N];
ull b[N];

inline int KMP(ull *a,int n){
  int k=; nxt[]=;
  for (int i=;i<=n;i++){
    while (k && a[k+]!=a[i]) k=nxt[k];
    if (a[k+]==a[i]) k++;
    nxt[i]=k;
  }
  for (int i=;i<=n;i++) b[i]=b[n+i]=a[i];
  k=; int ret=;
  for (int i=;i<n+n;i++){
    while (k && a[k+]!=b[i]) k=nxt[k];
    if (a[k+]==b[i]) k++;
    if (k==n) k=nxt[k],ret++;
  }
  if (n>){
    reverse(b+,b+n+n+); k=;
    for (int i=;i<n+n;i++){
      while (k && a[k+]!=b[i]) k=nxt[k];
      if (a[k+]==b[i]) k++;
      if (k==n) k=nxt[k],ret++;
    }
  }
  return ret;
}

inline void dfs(int u,int fa){
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa)
      dfs(V,u);
  pnt=;
  if (u<=n){
    for (int p=head[u];p;p=G[p].next)
      if (V!=fa)
    lst[++pnt]=H[V];
    sort(lst+,lst+pnt+);
    int tmp=;
    for (int i=;i<=pnt;i++){
      tmp++;
      if (i==pnt || lst[i]!=lst[i+])
    _q[tmp]++,tmp=;
    }
    H[u]=ORI1;
    for (int i=;i<=pnt;i++) (((H[u]*=BASE1)+=lst[i])^=lst[i])+=lst[i];
    ((H[u]+=END1)*=END1)^=END1;
  }else if (u!=rt){
    int k;
    for (int p=head[u];p;p=G[p].next)
      if (V==fa) { k=p; break; }
    for (int p=G[k].next;p;p=G[p].next)
      lst[++pnt]=H[V];
    for (int p=head[u];p!=k;p=G[p].next)
      lst[++pnt]=H[V];
    ull H1,H2;
    H1=ORI2;
    for (int i=;i<=pnt;i++) (((H1*=BASE2)+=lst[i])^=lst[i])+=lst[i];
    ((H1+=END2)*=END2)^=END2;
    H2=ORI2;
    for (int i=pnt;i;i--) (((H2*=BASE2)+=lst[i])^=lst[i])+=lst[i];
    ((H2+=END2)*=END2)^=END2;
    H[u]=min(H1,H2);
    if (pnt>= && H1==H2)
      _q[2]++;
  }else{
    for (int p=head[u];p;p=G[p].next)
      if (V!=fa)
    lst[++pnt]=H[V];
    int ret=KMP(lst,pnt),t=ret;
    for (int i=;i<=num && prime[i]<=ret;i++)
      while (t%prime[i]==)
    t/=prime[i],q[prime[i]]++;
  }
}

namespace Cac{
  struct edge{
    int u,v,next;
  }G[N<<];
  int head[N],inum=;
  inline void add(int u,int v){
    int p=++inum; G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
  }
  set<abcd> Set;
  inline void Add(int u,int v){
    if (u>v) swap(u,v); if (!Set.count(abcd(u,v))) Set.insert(abcd(u,v)),add(u,v),add(v,u);
  }
  int pre[N],low[N],clk;
  stack<int> sta;
  inline void dfs(int u,int fa){
    pre[u]=low[u]=++clk; sta.push(u);
    for (int p=head[u];p;p=G[p].next)
      if (p^fa^)
    if (!pre[V]){
      dfs(V,p);
      low[u]=min(low[u],low[V]);
      if (low[V]>=pre[u]){
        ++bcc;
        while (sta.top()!=u){
          int t=sta.top(); sta.pop();
          ::add(n+bcc,t),::add(t,n+bcc);
          if (t==V) break;
        }
        ::add(n+bcc,u); ::add(u,n+bcc);
      }
    }else
      low[u]=min(low[u],pre[V]);
  }
  inline void Read(){
    int k,x,y;
    read(m);
    while (m--){
      read(k); read(x);
      for (int i=;i<=k;i++)
    read(y),Add(x,y),x=y;
    }
    dfs(,);
  }
}

int main(){
  freopen("cactus.in","r",stdin);
  freopen("cactus.out","w",stdout);
  read(n); Pre(n<<);
  Cac::Read();
  Root(,);
  dfs(rt,);
  Print(n<<);
  return ;
}