[HNOI/AHOI2018] 毒瘤

· · 题解

在一些科技普及之后这个题好像就没什么意义了？

因为 m\leq n+10，所以根据广义串并联图的相关理论，我们可以通过 删一度点，缩二度点，叠合重边 的方式把原图缩成一个点数不超过 20，边数不超过 30 的图，其中每条边代表了原图的一个连通子图，且每条边对应的连通子图与外部的点只有恰好两个点连接，因此我们记录这两个点的状态就行了。

我们可以发现：

对于每条边 e ，设 f_{e,0/1,0/1} 代表与边 e 相连的两个点选的状态是 0/1,0/1 时，该边对应的连通子图内的方案数，g_{x,0/1} 代表 x 的状态时 0/1 时通过 删一度点 操作挂在 x 上的子图内的方案数，那么上述三操作对应的 f 和 g 的转移是简单的。

最后剩下的图中不超过 20 个点，我们 2^{20} 枚举然后把系数乘起来就好了。

复杂度 \Theta(n\log n+2^{2(m-n)}(m-n)) ，跑不满。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
map<int,int> mp[N];
int f[N][2][2],U[N],V[N];
int w[N][2],deg[N];
int n,m;
queue<int> q;
bool del[N];
inline int F(int e,int x,int c,int y,int d)
{
    if(x==U[e])return f[e][c][d];
    return f[e][d][c];
}
const int mod = 998244353;
int tmp[2][2];
int id[N],tot=0;
int seq[N],Eu[N],Ev[N],Ew[N][2][2];
int state[N];
bool ban[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)w[i][0]=w[i][1]=1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&U[i],&V[i]);
        if(mp[U[i]][V[i]])continue;
        mp[U[i]][V[i]]=i;
        mp[V[i]][U[i]]=i;
        f[i][0][0]=f[i][1][0]=f[i][0][1]=1;
        deg[U[i]]++;deg[V[i]]++;
    }
    for(int i=1;i<=n;i++)if(deg[i]<=2)q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(del[x])continue;
        if(deg[x]==0)continue;
        del[x]=1;
        if(deg[x]==1)
        {
            auto A=(*mp[x].begin());mp[x].erase(mp[x].begin());
            int y=A.first,e=A.second;
            deg[y]--;mp[y].erase(x);deg[x]=0;
            ban[e]=1;
            for(int c=0;c<=1;c++)
            {
                int v=0;
                for(int d=0;d<=1;d++)
                v=(v+1ll*w[x][d]*F(e,x,d,y,c)%mod)%mod;
                w[y][c]=1ll*w[y][c]*v%mod;
            }
            if(deg[y]<=2)q.push(y);
            continue;
        }
        auto A=(*mp[x].begin());mp[x].erase(mp[x].begin());
        auto B=(*mp[x].begin());mp[x].erase(mp[x].begin());
        int yA=A.first,eA=A.second;
        int yB=B.first,eB=B.second;
        int eC=mp[yA][yB];
        deg[x]=0;
        mp[yA].erase(x);mp[yB].erase(x);
        for(int a=0;a<=1;a++)//yA
        for(int b=0;b<=1;b++)//yB
        {
            tmp[a][b]=0;
            for(int c=0;c<=1;c++)
            tmp[a][b]=(tmp[a][b]+1ll*F(eA,yA,a,x,c)*F(eB,yB,b,x,c)%mod*w[x][c]%mod)%mod;
        }
        U[eA]=yA;V[eA]=yB;
        for(int a=0;a<=1;a++)
        for(int b=0;b<=1;b++)
        f[eA][a][b]=tmp[a][b];
        mp[yA][yB]=mp[yB][yA]=eA;
        if(eC)
        {
            for(int a=0;a<=1;a++)
            for(int b=0;b<=1;b++)
            f[eA][a][b]=1ll*f[eA][a][b]*F(eC,yA,a,yB,b)%mod;
            deg[yA]--;deg[yB]--;
            if(deg[yA]<=2)q.push(yA);
            if(deg[yB]<=2)q.push(yB);
            ban[eC]=1;
        }
    }
    for(int x=1;x<=n;x++)if(!del[x])
    {
        seq[++tot]=x;
        id[x]=tot;
    }
    int C=0;
    for(int x=1;x<=n;x++)if(!del[x])
    {
        for(auto U:mp[x])
        {
            int y=U.first,e=U.second;
            if(x<y)
            {
                ++C;
                Eu[C]=id[x];
                Ev[C]=id[y];
                for(int a=0;a<=1;a++)
                for(int b=0;b<=1;b++)
                Ew[C][a][b]=F(e,x,a,y,b);
            }
        }
    }
    int ans=0;
    for(int S=0;S<(1<<tot);S++)
    {
        int res=1;
        for(int i=1;i<=tot;i++)
        {
            state[i]=((S>>(i-1))&1);
            res=1ll*res*w[seq[i]][state[i]]%mod;
        }
        for(int i=1;i<=C;i++)
        res=1ll*res*Ew[i][state[Eu[i]]][state[Ev[i]]]%mod;
        ans=(ans+res)%mod;
    }
    cout<<ans;
    return 0;
}