题解 P4426 【[HNOI/AHOI2018]毒瘤】

· · 题解

考虑直接暴力。

f[x][1]=f[x][1]*f[y][0];
f[x][0]=f[x][0]*(f[y][0]+f[y][1]);

那么显然，对于一条非树边，只有两种状态，并不是三种，我们直接二进制枚举这些状态，把不合法的continue掉，卡卡常就过了。理论复杂度有2e8，但是luogu开了O2可以在1s之内跑出来。

#include <bits/stdc++.h>
using namespace std;
namespace IO
{
    const int __S=(1<<21)+5;char __buf[__S],*__H,*__T;
    inline char getc()
    {
        if(__H==__T) __T=(__H=__buf)+fread(__buf,1,__S,stdin);
        if(__H==__T) return -1;return *__H++;
    }
    template <class __I>inline void read(__I &__x)
    {
        __x=0;int __fg=1;char __c=getc();
        while(!isdigit(__c)&&__c!='-') __c=getc();
        if(__c=='-') __fg=-1,__c=getc();
        while(isdigit(__c)) __x=__x*10+__c-'0',__c=getc();
        __x*=__fg;
    }
    inline void readd(double &__x)
    {
        __x=0;double __fg=1.0;char __c=getc();
        while(!isdigit(__c)&&__c!='-') __c=getc();
        if(__c=='-') __fg=-1.0,__c=getc();
        while(isdigit(__c)) __x=__x*10.0+__c-'0',__c=getc();
        if(__c!='.'){__x=__x*__fg;return;}else while(!isdigit(__c)) __c=getc();
        double __t=1e-1;while(isdigit(__c)) __x=__x+1.0*(__c-'0')*__t,__t=__t*0.1,__c=getc();
        __x=__x*__fg;
    }
    inline void reads(char *__s,int __x)
    {
        char __c=getc();int __tot=__x-1;
        while(__c<'!'||__c>'~') __c=getc();
        while(__c>='!'&&__c<='~') __s[++__tot]=__c,__c=getc();
        __s[++__tot]='\0';
    }
    char __obuf[__S],*__oS=__obuf,*__oT=__oS+__S-1,__c,__qu[55];int __qr;
    inline void flush(){fwrite(__obuf,1,__oS-__obuf,stdout);__oS=__obuf;}
    inline void putc(char __x){*__oS++ =__x;if(__oS==__oT) flush();}
    template <class __I>inline void print(__I __x)
    {
        if(!__x) putc('0');
        if(__x<0) putc('-'),__x=-__x;
        while(__x) __qu[++__qr]=__x%10+'0',__x/=10;
        while(__qr) putc(__qu[__qr--]);
    }
    inline void prints(const char *__s,const int __x)
    {
        int __len=strlen(__s+__x);
        for(int __i=__x;__i<__len+__x;__i++) putc(__s[__i]);
    }
    inline void printd(double __x,int __d)
    {
        long long __t=(long long)floor(__x);print(__t);putc('.');__x-=(double)__t;
        while(__d--)
        {
            double __y=__x*10.0;__x*=10.0;
            int __c=(int)floor(__y);
            putc(__c+'0');__x-=floor(__y);
        }
    }
    inline void el(){putc('\n');}inline void sp(){putc(' ');}
}using namespace IO;
#define N 100100
#define P 998244353
int n,m,x,y,ok,cnt,ans,he[N],ne[N*2],to[N*2],f[N],g[N],u[N],v[N],a[N],b[N],dfn[N],d[N],I,t1,t2,t3;
void add(int x,int y){to[cnt]=y;ne[cnt]=he[x];he[x]=cnt++;}
int inc(int x,int y){return x+y>=P?x+y-P:x+y;}
void dfs(int x,int fa)
{
    dfn[x]=++I;
    for(int i=he[x],y;~i;i=ne[i]) if((y=to[i])!=fa)
    {
        if(dfn[y]&&dfn[y]<dfn[x]) a[++t1]=y,b[t1]=x,d[++t3]=y,d[++t3]=x;
        else if(!dfn[y]) u[++t2]=x,v[t2]=y,dfs(y,x);
    }
}
int main()
{
    read(n);read(m);memset(he,-1,sizeof(he));
    for(register int i=1;i<=m;i++) read(x),read(y),add(x,y),add(y,x);
    dfs(1,0);
    for(register int s=0;s<(1<<t1);s++)
    {
        for(register int i=1;i<=n;i++) f[i]=g[i]=1;
        for(register int i=1;i<=t1;i++) if((1<<(i-1))&s) g[a[i]]=0;else f[a[i]]=g[b[i]]=0;
        ok=1;for(int i=1;i<=t3;i++) if(!f[d[i]]&&!g[d[i]]){ok=0;break;}
        if(!ok) continue;
        for(register int i=n-1;i;i--) x=u[i],y=v[i],f[x]=1ll*f[x]*(f[y]+g[y])%P,g[x]=1ll*g[x]*f[y]%P;
        ans=inc(ans,inc(f[1],g[1]));
    }
    printf("%d\n",ans);
}