Luogu P4426 [HNOI/AHOI2018]毒瘤

题目

神仙题。

首先我们可以把题意转化为图的独立集计数。显然这个东西是个NP-Hard的。

然后我们可以注意到\(m\le n+10\)，也就是说最多有\(11\)条非树边。

我们现在先考虑一下，树上独立集计数怎么做。

设\(f_{u,0/1}\)表示\(u\)点选/不选的方案数。

那么转移方程就是：

\(f_{u,0}=\prod\limits_{v\in son_u}(f_{v,0}+f_{v,1})\)

\(f_{u,1}=\prod\limits_{v\in son_u}f_{v,0}\)

最后的答案就是\(f_{1,0}+f_{1,1}\)。

然后我们知道现在有最多\(11\)条非树边，我们可以枚举每条非树边两端的状态，然后再跑一遍dp。

这样每条非树边有\((0,0),(0,1),(1,0)\)三种情况。可以发现\((0,0),(0,1)\)这两种情况可以合并。这样就变成枚举每条非树边的起点选不选。

所以我们就得到了一个\(O(n2^{m-n+1})\)的优秀做法。根据常数可以获得\(70\sim80\)分的好成绩。

然后我们来想一件事情，我们每次做dp的时候，有很多转移是浪费的。

我们可以把每个点的\(f\)看做一个向量，那么转移就可以看做是一个矩阵。

然后我们会发现转移基本上都是不变的，变的只是我们枚举强制选不选的那些点的向量。

这启发我们用虚树来处理dp部分。

把枚举强制选不选的那些点看做是关键点，然后对于它们建一棵虚树，然后dp。

所以现在我们需要求的就是虚树上的一条边（对应原树上的一条链）的转移的系数，这个东西我们可以通过在原树上自下而上dfs一遍求得。这个过程可能有点麻烦。

实际上建虚树的过程也可以在上面这个dfs的过程中来完成。

然后我们就可以在虚树上面跑dp了，时间复杂度为\(O(n+(m-n+1)2^{m-n+1})\)。

#include<bits/stdc++.h>

#define pb push_back

#define pi pair<int,int>

#define fi first

#define se second

using namespace std;

namespace IO

{

    char ibuf[(1<<21)+1],*iS,*iT;

    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}

    int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}

}using namespace IO;

const int N=100020,P=998244353;

int inc(int a,int b){return a+=b,a>=P? a-P:a;}

int mul(int a,int b){return 1ll*a*b%P;}

int n,m;

namespace Graph

{

    vector<int>E[N];int T,cnt,dfn[N],size[N],vis[N],fa[N];

    struct edge{int u,v;}e[N];

    void add(int u,int v){E[u].pb(v),E[v].pb(u);}

    void dfs(int u)

    {

	dfn[u]=++T;

	for(int v:E[u])

	    if(v^fa[u])

		if(!dfn[v]) fa[v]=u,dfs(v),size[u]+=size[v];

		else if(dfn[v]<dfn[u]) e[++cnt]={u,v},vis[u]=vis[v]=1;

	vis[u]|=size[u]>=2,size[u]=size[u]||vis[u];

    }

}using namespace Graph;

namespace ITree

{

    int f[N][2],g[N][2],p[N][2],is[N];pi k[N][2];

    pi operator+(pi a,pi b){return pi(inc(a.fi,b.fi),inc(a.se,b.se));}

    pi operator*(pi a,int k){return pi(mul(k,a.fi),mul(k,a.se));}

    struct node{int v;pi a,b;};vector<node>G[N];

    void Add(int u,int v,pi a,pi b){G[u].pb({v,a,b});}

    int build(int u)

    {

	p[u][0]=p[u][1]=1,is[u]=1;int pos=0,w;

	for(int v:E[u])

	    if(!is[v])

	    {

		w=build(v);

		if(!w) p[u][1]=mul(p[u][1],p[v][0]),p[u][0]=mul(p[u][0],inc(p[v][0],p[v][1]));

		else if(vis[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][0]+k[v][1],pos=w;

	    }

	if(vis[u]) k[u][0]=pi(1,0),k[u][1]=pi(0,1),pos=u; else k[u][0]=k[u][0]*p[u][0],k[u][1]=k[u][1]*p[u][1];

	return pos;

    }

    void dp(int u)

    {

	(f[u][0]=g[u][1]? 0:p[u][0]),(f[u][1]=g[u][0]? 0:p[u][1]);

	for(auto [v,a,b]:G[u])

	{

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

	    f[u][0]=mul(f[u][0],inc(mul(a.fi,p),mul(a.se,q)));

	    f[u][1]=mul(f[u][1],inc(mul(b.fi,p),mul(b.se,q)));

	}

    }

}using namespace ITree;

int main()

{

    n=read(),m=read();int ans=0;

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

    dfs(1),vis[1]=1,build(1);

    for(int S=0,i;S<1<<cnt;++S)

    {

	for(i=1;i<=cnt;++i) if(S>>(i-1)&1) g[e[i].u][1]=g[e[i].v][0]=1; else g[e[i].u][0]=1;

	dp(1),ans=inc(ans,inc(f[1][1],f[1][0]));

	for(i=1;i<=cnt;++i) if(S>>(i-1)&1) g[e[i].u][1]=g[e[i].v][0]=0; else g[e[i].u][0]=0;

    }

    printf("%d",ans);

}

巴特西

Luogu P4426 [HNOI/AHOI2018]毒瘤

最新文章

热门文章