欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.10.29 洛谷P4129 [SHOI2006]仙人掌(仙人掌+高精度)

程序员文章站 2022-05-22 10:16:50
...

传送门
显然求出每一个环的大小。
Ans=∏i(siz[i]+1)Ans=\prod_i(siz[i]+1)Ans=i(siz[i]+1)
注意用高精度存答案。
代码:

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
const int N=2e4+5,M=1e6+5;
int n,m,first[N],cnt=0,dfn[N],low[N],du[N],dep[N],fa[N],tot=0,siz=0;
struct edge{int v,next;}e[M<<1];
struct bignum{
    int s[N<<1],len;
    bignum(){memset(s,0,sizeof(s)),len=0;}
    inline bignum operator=(int x){
        while(x)s[++len]=x-x/10*10,x/=10;
        return *this;
    }
    inline bignum operator*(const bignum&x){
        bignum ret;
        int maxlen=x.len+len-1;
        for(int i=1;i<=len;++i)for(int j=1;j<=x.len;++j)ret.s[i+j-1]+=s[i]*x.s[j];
        for(int i=1;i<=maxlen;++i)if(ret.s[i]>=10)ret.s[i+1]+=ret.s[i]/10,ret.s[i]=ret.s[i]-ret.s[i]/10*10;
        while(ret.s[maxlen+1]){
            ++maxlen;
            if(ret.s[maxlen]>=10)ret.s[maxlen+1]+=ret.s[maxlen]/10,ret.s[maxlen]=ret.s[maxlen]-ret.s[maxlen]/10*10;
        }
        return ret.len=maxlen,ret;
    }
    inline void output(){for(int i=len;i;--i)printf("%d",s[i]);}
}ans;
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void calc(int st,int ed){
    for(int i=ed;i!=st;i=fa[i])if(++du[i]==2)puts("0"),exit(0);
    bignum tmp;
    tmp=(dep[ed]-dep[st]+2);
    ans=ans*tmp;
}
inline void tarjan(int p){
    ++siz;
    dfn[p]=low[p]=++tot;
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa[p])continue;
        if(!dfn[v])dep[v]=dep[p]+1,fa[v]=p,tarjan(v),low[p]=min(low[p],low[v]);
        else low[p]=min(low[p],dfn[v]);
    }
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(fa[v]!=p&&dfn[p]<dfn[v])calc(p,v);
    }
}
int main(){
    n=read(),m=read(),ans.len=ans.s[1]=1;
    while(m--){
        int k=read()-1,x=read(),y;
        while(k--)y=read(),add(y,x),add(x,y),x=y;
    }
    tarjan(1);
    if(siz!=n)puts("0"),exit(0);
    ans.output();
    return 0;
}