[ZJOI2017]仙人掌

C++14(g++5.4) 解法, 执行用时: 773ms, 内存消耗: 86744K, 提交时间: 2019-03-14 18:06:23

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
    char c=nc();int len=0;
    for(;!(c>='A' && c<='Z');c=nc()) if (c==EOF) return 0;
    for(;(c>='A' && c<='Z');s[len++]=c,c=nc());
    s[len++]='\0';
    return len;
}

inline void read(char &x){
  for (x=nc();!(x>='A' && x<='Z');x=nc());
}

int wt,ss[19];
inline void print(int x){

    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int T,n,m,s,flag,v[500010];
vector<int> b[500010];
LL g[500010],f[500010];
const LL mo=998244353;
struct tree
{
    int a,b,dfs,low;
}a[500010];
map<int,bool> c[500010];

int dep[500010],dfn[500010],fa[500010],lu[500010],cnt;

void init()
{
    for (int i=1;i<=n;i++)
        b[i].clear(),a[i].dfs=a[i].low=a[i].a=a[i].b=0,c[i].clear(),dfn[i]=0,dep[i]=0,fa[i]=0;
    g[1]=1LL,g[0]=1LL;
    for (int i=2;i<=n;i++)
        g[i]=(g[i-1]+g[i-2]*(LL)(i-1)%mo)%mo;
}

void dfs(int x,int p)
{
    fa[x]=p,dfn[x]=++cnt,dep[x]=dep[p]+1;
    for (int i=0;i<b[x].size();i++)
        if (!dfn[b[x][i]]) dfs(b[x][i],x);
}

bool check()
{
    cnt=0;
    dfs(1,0);
    int u,v;
    memset(lu,0,sizeof(lu));
    for (int i=1;i<=n;i++)
        for (int j=0;j<b[i].size();j++)
        if (i<b[i][j])
        {
            u=i,v=b[i][j];
            if (dfn[u]<dfn[v]) swap(u,v);
            while (u!=v)
            {
                if (lu[u]==2) return false;
                lu[u]++,u=fa[u];
            }
        }
    return true;
}

void dp(int x,int y)
{
    v[x]=1;f[x]=1;
    int sum=0;
    for (int i=0;i<b[x].size();i++)
        if (!v[b[x][i]] && !c[x][b[x][i]])
        {
            dp(b[x][i],y);
            f[x]=f[x]*f[b[x][i]]%mo;
            sum++;
        }
    if (x==y) f[x]=f[x]*g[sum]%mo;
    else f[x]=f[x]*g[sum+1]%mo;
}

void work(int x)
{
    for (int i=0;i<b[x].size();i++)
        if (v[b[x][i]] && b[x][i]!=fa[x])
        {
            int y=b[x][i];
            c[x][y]=1,c[y][x]=1;
            while (x!=y)
            {
                c[x][fa[x]]=1;c[fa[x]][x]=1;
                x=fa[x];
            }
            return ;
        }
        else if (!v[b[x][i]]) 
            v[b[x][i]]=1,fa[b[x][i]]=x,work(b[x][i]),v[b[x][i]]=0;
}

int main()
{
    read(T);
    while(T--)
    {
        read(n);read(m);
        int x,y;
        init();
        for (int i=1;i<=m;i++)
            read(x),read(y),b[x].push_back(y),b[y].push_back(x);
        if (!check()) {print(0),puts("");continue;}
        for(int i=1;i<=n;i++) v[i]=0;
        v[1]=1;work(1);
        LL res=1;
        for(int i=1;i<=n;i++) v[i]=0;
        for (int i=1;i<=n;i++)
            if (!v[i]) dp(i,i),res=res*f[i]%mo;
        print(res);puts("");
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 358ms, 内存消耗: 23672K, 提交时间: 2019-03-09 14:12:12

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

typedef long long ll;

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0' || '9'<ch)ch=getchar();
    while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
    return x;
}

const int N=5e5+9;
const int M=1e6+9;
const int md=998244353;

int to[M],nxt[M],beg[N],tot;
int n,m,fa[N],dep[N],dfn[N],path[N],a[N],dfs_clock;
ll f[N],g[N],ans;

inline void adde(int u,int v)
{
    to[++tot]=v;
    nxt[tot]=beg[u];
    beg[u]=tot;
}

inline void add(int u,int v)
{
    adde(u,v),adde(v,u);
}

void dfs(int u)
{
    dfn[u]=++dfs_clock;

    for(int i=beg[u],v;i;i=nxt[i])
        if((v=to[i])!=fa[u] && !dfn[v])
        {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs(v);
        }
}

inline bool cmp(int a,int b)
{
    return dep[a]<dep[b];
}

void dfs2(int u,bool isrt)
{
    f[u]=1;
    path[u]=-1;
    int soncnt=0;

    for(int i=beg[u],v;i;i=nxt[i])
        if((v=to[i])!=fa[u] && path[v]==1)
        {
            soncnt++;
            dfs2(v,0);
            (f[u]*=f[v])%=md;
        }

    if(soncnt==0)
        return;

    if(isrt)
        (f[u]*=g[soncnt])%=md;
    else
        (f[u]*=g[soncnt+1])%=md;
}

int main()
{
    g[0]=g[1]=1;
    for(int i=2;i<N;i++)
        g[i]=(g[i-1]+g[i-2]*(i-1))%md;

    int T=read();
    while(T--)
    {
        n=read();
        m=read();

        tot=1;
        for(int i=1;i<=n;i++)
            beg[i]=fa[i]=dfn[i]=dep[i]=path[i]=0;

        for(int i=1;i<=m;i++)
            add(read(),read());

        tot=0;
        dep[1]=1;
        fa[1]=0;
        dfs(1);

        for(int i=1;i<=m;i++)
        {
            int st=to[i<<1],ed=to[i<<1|1];
            if(dfn[st]<dfn[ed])
                swap(st,ed);

            while(st!=ed)
            {
                path[st]++;
                if(path[st]>2)
                    goto wa;
                st=fa[st];
            }
        }

        if(0)
        {
            wa:;
            puts("0");
            continue;
        }

        for(int i=1;i<=n;i++)
            a[i]=i;
        sort(a+1,a+n+1,cmp);

        ans=1ll;
        for(int i=1;i<=n;i++)
            if(path[a[i]]!=-1)
            {
                dfs2(a[i],1);
                (ans*=f[a[i]])%=md;
            }

        printf("%lld\n",ans);
    }

    return 0;
}

详情