题面链接

sol

这篇博是骗访问量的QwQ。

考虑树怎么做，简单容斥。诸如\(f[u][0]=\prod (f[v][0]+f[v][1]),f[u][1]=\prod f[v][0]\)

考虑\(80\)分怎么做(其实只有\(75\)分)，暴力枚举多出来的边链接情况，然后\(dp\)，复杂度\(O(2^{m-n+1}n)\)。

考虑\(100\)分怎么做，发现只有\(22\)个有用的点，于是建虚树，预处理转移系数，有点复杂。复杂度\(O((m-n+1)*2^{m-n+1}+n)\)

upd:系数大概是个\(f[u][i]=\sum w[u->v][j][i]*f[v][j]\)。自己YY一下就好了，可以拓展到多维系数。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

inline int in()

{

    int k=0;char ch=gt;

    while(ch<'-')ch=gt;

    while(ch>'-')k=k*10+ch-'0',ch=gt;

    return k;

}

const int N=2e5+5,YL=998244353;

int f[N][2],fg[N][2],le[N],ri[N],top;

int head[N],to[N<<1],nxt[N<<1],cnt,imp[N];

inline void add(int u,int v)

{

    to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;

    to[++cnt]=u,nxt[cnt]=head[v],head[v]=cnt;

}

inline int MO(const int &a){return a>=YL?a-YL:a;}

int dfn[N],low[N],tt,tsz[N];

void dfs(int u,int pa=0)

{

    dfn[u]=++tt;

    for(int i=head[u];i;i=nxt[i])

        if(to[i]!=pa)

        {

            if(!dfn[to[i]])dfs(to[i],u),tsz[u]+=tsz[to[i]];

            else if(dfn[u]<dfn[to[i]])le[++top]=u,ri[top]=to[i],imp[u]=1;

            else imp[u]=1;

        }

    imp[u]|=tsz[u]>=2;tsz[u]=imp[u]||tsz[u];

}

int o[N];

int Head[N],To[N],Nxt[N];

struct bj

{

    int x,y;

    bj(){x=0,y=0;}

    bj(int _x,int _y):x(_x),y(_y){}

    inline bj operator+(const bj  &a){return bj(x+a.x,y+a.y);}

    inline bj operator*(const int &a){return bj(1ll*x*a%YL,1ll*y*a%YL);}

}W1[50],W2[50],k[N][2];

inline void Add(int u,int v,bj a,bj b){To[++cnt]=v,Nxt[cnt]=Head[u],W1[cnt]=a,W2[cnt]=b,Head[u]=cnt;}

int g[N][2];

int Dfs(int u,int pa=0)

{

    g[u][0]=g[u][1]=1;o[u]=1;int pos=0,w;

    for(int i=head[u];i;i=nxt[i])

        if(!o[to[i]])

        {

            int v=to[i];w=Dfs(v);

            if(!w)g[u][1]=1ll*g[u][1]*g[v][0]%YL,g[u][0]=1ll*g[u][0]*(g[v][1]+g[v][0])%YL;

            else if(imp[u])Add(u,w,k[v][0]+k[v][1],k[v][0]);

            else k[u][1]=k[v][0],k[u][0]=k[v][1]+k[v][0],pos=w;

        }

    if(imp[u])k[u][0]=bj(1,0),k[u][1]=bj(0,1),pos=u;

    else k[u][0]=k[u][0]*g[u][0],k[u][1]=k[u][1]*g[u][1];

    return pos;

}

void dp(int u)

{

    f[u][0]=fg[u][1]?0:g[u][0];

    f[u][1]=fg[u][0]?0:g[u][1];

    for(int i=Head[u];i;i=Nxt[i])

        {

            int v=To[i];dp(v);int p=f[v][0],q=f[v][1];

            f[u][1]=1ll*f[u][1]*(1ll*W2[i].x*p%YL+1ll*W2[i].y*q%YL)%YL;

            f[u][0]=1ll*f[u][0]*(1ll*W1[i].x*p%YL+1ll*W1[i].y*q%YL)%YL;

        }

}

int main()

{

    int n=in(),m=in();

    for(int i=1;i<=m;++i)add(in(),in());cnt=0;

    dfs(1);imp[1]=1;Dfs(1);

    int S=1<<top,ans=0;

    for(int i=0;i<S;++i)

    {

        for(int j=0;j<top;++j)

            if(i>>j&1)fg[le[j+1]][1]=fg[ri[j+1]][0]=1;

            else fg[le[j+1]][0]=1;

        dp(1);ans=MO(ans+MO(f[1][1]+f[1][0]));

        for(int j=0;j<top;++j)

            if(i>>j&1)fg[le[j+1]][1]=fg[ri[j+1]][0]=0;

            else fg[le[j+1]][0]=0;

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

HNOI2018毒瘤

题面链接

sol

最新文章

热门文章