注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3899]仙人掌树的同构  

2015-06-20 19:26:32|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3899: 仙人掌树的同构

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 24  Solved: 9
[Submit][Status][Discuss]

Description

首先,先介绍仙人掌树。仙人掌树是一张无向图,但是每个节点最多只会在一个环里面,而且这张图的环全部都是简单环,即A->B->C->A这种。
比如下图就是一颗仙人掌树。
 
好的,知道了仙人掌树之后,我们现在要计算一个东西。
我们现在已经知道了一个N个节点的仙人掌树,称作为原图。接下来,我们要用1-N的一个排列A[1]-A[N]去变换这棵树,具体的,如果原图中有一条边i-j,那么变换出来的图中必须有一条A[i]-A[j]的边。同样的,如果变换出来的图中有一条A[i]-A[j]的边,那么原图中必有一条i-j的边。(简单而言就是点重新编号)
小A为了超脱宇宙的束缚,必须要知道,有多少种排列,可以使得变换出来的新图和原图是一模一样的,具体的,原图中如果存在一条i-j的边,新图也存在一条i-j的边,新图中存在一条i-j的边,原图中也存在i-j的边。
方案数目答案mod 1000000003。

Input

第一行有两个正整数,N和M,节点个数和边的个数。
接下来M行,每行有2个正整数S,T,表示一条原图的无向边。数据保证没有重边。

Output

一行一个正整数表示方案书目。

Sample Input

5 5 1 2 2 3 3 4 4 5 1 5

Sample Output

10

HINT

所有的答案包括(i,(i+1) % 5 + 1,(i+2) % 5 + 1,(i+3) % 5 + 1,(i+4) % 5 + 1)和(i,(i+4) % 5 + 1,(i+3) % 5 + 1,(i+2) % 5 + 1,(i+1) % 5 + 1)这两种类型。每种类型的i可以是12345,所以答案是2*5=10。
N<=1000

Solution

首先随便拿一个点root当根,递归计算x的儿子,calc(x)表示以x为顶点的子树内同构的方案数。
x的链儿子:如果有j个孩子长的一模一样的话,f[x]*=j!,显然随便交换他们的顺序是无所谓的。
x的环兄弟:环是有顺序的,不能任意交换,不过如果环是左右对称的话,可以把环翻过来,做一个对称变换,f[x]*=2
然而还有一种情况,光是上面的两条样例都算不来:
ans=f[root]*sigma( 以root为根的树与以i为根的树相等 (i=[1,n]))

Code

/**************************************************************
    Problem: 3899
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:588 ms
    Memory:952 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1010
#define p 1000000003
#define min(a,b) (a<b?a:b)
int n,m,et=1,la[N],fac[N]={1},x,y,col[N],cnt,vis[N],fa[N],siz[N],f[N],ans,loop[N];long long num[N],son[N],same;
struct E{int to,nxt,flag;}e[N<<3];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void dfs(int x,int f){
    vis[x]=1;fa[x]=f;
    for(int i=la[x];i;i=e[i].nxt)if(e[i].to!=f)
    if(vis[e[i].to]){
        if(col[e[i].to])continue;
        siz[++cnt]=1;col[e[i].to]=cnt;fa[e[i].to]=x;
        for(int y=x;y!=e[i].to&&y;y=fa[y])siz[cnt]++,col[y]=cnt;
    }
    else dfs(e[i].to,x);
}
void calc(int x,int dep){
    f[x]=1,num[x]=1;
    for(int i=la[x];i;i=e[i].nxt)if(e[i].flag==0)
    if(col[e[i].to]!=col[x]){
        e[i].flag=e[i^1].flag=1;
        calc(e[i].to,dep+1);
        f[x]=1LL*f[x]*f[e[i].to]%p;
        e[i].flag=e[i^1].flag=0;
    }
    int m=0,sm=1;
    if(vis[col[x]]!=2&&siz[col[x]]!=1){
        vis[col[x]]=2;
        for(int y=fa[x];y!=x;y=fa[y])
        calc(y,dep+1),f[x]=1LL*f[x]*f[y]%p;
        for(int y=fa[x];y!=x;y=fa[y])loop[++m]=y;
        for(int i=1,j=m;i<=j;i++,j--)if(num[loop[i]]!=num[loop[j]])sm=0;
        if(sm)f[x]=2LL*f[x]%p;
        vis[col[x]]=0;
    }
    int t=0,j=1;
    for(int i=la[x];i;i=e[i].nxt)
    if(col[x]!=col[e[i].to])son[++t]=num[e[i].to];
    std::sort(son+1,son+1+t);
    for(int i=2;i<=t;i++)
    if(son[i]==son[i-1])j++;else f[x]=1LL*f[x]*fac[j]%p,j=1;
    f[x]=1LL*f[x]*fac[j]%p;
    for(int i=1;i<=m;i++)son[++t]=num[loop[i]]*(233+siz[col[x]])+min(i,m+1-i);
    std::sort(son+1,son+1+t);
    for(int i=1;i<=t;i++)num[x]=num[x]*131+son[i];
    num[x]=num[x]*dep;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fac[i]=1LL*fac[i-1]*i%p;
    for(;m--;scanf("%d%d",&x,&y),add(x,y),add(y,x));
    dfs(1,0);
    for(int i=1;i<=n;i++)if(!col[i])col[i]=++cnt,siz[cnt]=1;
    calc(1,1);
    ans=f[1],same=num[1];int cnt0=1;
    for(int i=2;i<=n;i++){
        memset(num,0,sizeof(num));
        calc(i,1);
        if(same==num[i])cnt0++;
    }
    printf("%lld\n",1LL*ans*cnt0%p);
}
  评论这张
 
阅读(366)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018