2 条题解

  • 0
    @ 2026-7-5 9:33:54 

    #include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 100005;
const int MOD = 998244353;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,t,cnt,ans,ea[M],eb[M],dfn[M],mark[M],sz[M];
vector<int> g[M],ng[M];int f[M][2],fl[M][2],p[M][2];
struct node
{
	int x,y;node(int X=0,int Y=0) : x(X) , y(Y) {}
	node operator + (const node &b) const
		{return node((x+b.x)%MOD,(y+b.y)%MOD);}
	node operator * (const int &b) const
		{return node(x*b%MOD,y*b%MOD);}
}k[M][2],o[M][2];
void dfs(int u,int fa)
{
	dfn[u]=++cnt;
	for(int v:g[u]) if(v!=fa)
	{
		if(!dfn[v]) dfs(v,u),sz[u]+=sz[v];
		else
		{
			mark[u]=1;
			if(dfn[u]<dfn[v]) ea[++t]=u,eb[t]=v;
		}
	}
	mark[u]|=sz[u]>=2;sz[u]=sz[u]||mark[u];
}
int pre(int u)
{
	p[u][0]=p[u][1]=1;dfn[u]=1;int pos=0;
	for(int v:g[u]) if(!dfn[v])
	{
		int w=pre(v);
		if(!w)
		{
			p[u][0]=p[u][0]*(p[v][0]+p[v][1])%MOD;
			p[u][1]=p[u][1]*p[v][0]%MOD;
		}
		else if(mark[u])
		{
			ng[u].push_back(w);
			o[w][0]=k[v][0]+k[v][1];
			o[w][1]=k[v][0];
		}
		else k[u][1]=k[v][0],k[u][0]=k[v][0]+k[v][1],pos=w;
	}
	if(mark[u]) k[u][0]=node(1,0),k[u][1]=node(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 calc(int u)
{
	f[u][0]=fl[u][0]?0:p[u][0];
	f[u][1]=fl[u][1]?0:p[u][1];
	for(int v:ng[u])
	{
		calc(v);int p=f[v][0],q=f[v][1];
		f[u][0]=f[u][0]*((p*o[v][0].x+q*o[v][0].y)%MOD)%MOD;
		f[u][1]=f[u][1]*((p*o[v][1].x+q*o[v][1].y)%MOD)%MOD;
	}
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);mark[1]=1;
	memset(dfn,0,sizeof dfn);pre(1);
	for(int i=0;i<(1<<t);i++)
	{
		for(int j=1;j<=t;j++)//1:choose ; 0:not choose
			if(i&(1<<j-1)) fl[ea[j]][0]=fl[eb[j]][1]=1;
			else fl[ea[j]][1]=1;
		calc(1);
		ans=(ans+f[1][0]+f[1][1])%MOD;
		for(int j=1;j<=t;j++)
			if(i&(1<<j-1)) fl[ea[j]][0]=fl[eb[j]][1]=0;
			else fl[ea[j]][1]=0;
	}
	printf("%lld\n",ans);
}
    • 0
      @ 2026-5-7 1:20:17

      题意

      求一幅图的最大独立集方案数

      n≤105,n\le10^5,满足非树边≤11\le11条

      AFOAFO之后这篇题解搁了好久=.==.=

      题解

      1.1.考虑一棵树怎么做

      和普通求独立集一样枚举这个点选不选然后用乘法原理计算即可

      f[u][1]=f[u][1]*f[v][0];
f[u][0]=f[u][0]*(f[v][0]+f[v][1]);

      2.2.考虑怎么处理非树边

      因为只有1111条非树边,,所以可以枚举这些边的两个端点的选择情况

      可以发现只有33种情况(1,0),(0,0),(0,1)(1,0),(0,0),(0,1)

      但是实际上可以发现只需要枚举上面那个点选不选,,即(0,0)(0,0)和(0,1)(0,1)可以合并起来

      然后对于每一种状态再朴素做一遍树DPDP

      复杂度O(2m−n+1n)O(2^{m-n+1}n)

      #include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,P=998244353;
typedef int arr[N];
typedef long long ll;
struct eg{int nx,to;}e[N<<1];
int n,m,ans,dft,Cnt,f[N][2],fg[N][2];arr fi,fa,eu,ev,Mi,dfn,vis;
inline int pls(int a,int b){return a+=b,a<P?a:a-P;}
void dfs(int u){
    dfn[u]=++dft;
    go(u)if(v^fa[u]){
        if(!dfn[v])fa[v]=u,dfs(v);
        else if(dfn[u]<dfn[v])eu[++Cnt]=u,ev[Cnt]=v;
    }
}
void dp(int u){
    f[u][0]=!fg[u][1],f[u][1]=!fg[u][0],vis[u]=1;
    go(u)if(!vis[v]){
        dp(v);
        f[u][1]=(ll)f[u][1]*f[v][0]%P;
        f[u][0]=(ll)f[u][0]*(f[v][0]+f[v][1])%P;
    }
}
inline void add(int u,int v){static int ce=0;e[++ce]={fi[u],v},fi[u]=ce;}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n),sd(m);int u,v;
    fp(i,1,m)sd(u),sd(v),add(u,v),add(v,u);
    dfs(1);Mi[1]=1;fp(i,2,Cnt)Mi[i]=Mi[i-1]<<1;
    fp(s,0,(1<<Cnt)-1){
        fp(i,1,Cnt)
            if(s&Mi[i])fg[eu[i]][1]=fg[ev[i]][0]=1;
            else fg[eu[i]][0]=1;
        fp(i,1,n)vis[i]=0;dp(1);ans=pls(ans,pls(f[1][1],f[1][0]));
        fp(i,1,Cnt)
            if(s&Mi[i])fg[eu[i]][1]=fg[ev[i]][0]=0;
            else fg[eu[i]][0]=0;
    }
    printf("%d\n",ans);
return 0;
}

      这样就可以拿到7575分了

      3.3.考虑怎么优化

      可以发现上面的暴力算法中有很多状态都是重复计算了的

      我们把连有非树边的点当做关键点

      因为每次影响DPDP值的就只有这些关键点

      所以我们考虑建出这2222个关键点的虚树

      对于虚树上一条边u→v,dpu\to v,dp方程可以化为

      $$f[u][0/1]=\prod k_{v,0/1,0}f[v][0]+k_{v,0/1,1}f[v][1]$$

      可以发现每条边的系数是不会改变的

      所以关键就在于怎么求出每一条边的系数

      对于一条虚树边u→v,u\to v,将原树中u→vu\to v的路径提出来

      从vv节点向上跳并暴力转移系数,,若遇到分叉则额外转移上分叉处的系数

      如果遇到一个新的关键点就重置系数

      根据虚树的性质,,一个分叉点要么是关键点要么子树里就一个关键点

      可以发现这样转移的总复杂度是O(n)O(n)的

      对于虚树上的边我们还是按照上面的想法枚举端点的情况

      令s=m−n+1,s=m-n+1,那么复杂度就是O(n+s2s)O(n+s2^s)

      #include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+15,P=998244353;
typedef int arr[N];
typedef long long ll;
struct eg{int nx,to;}e[N<<1];
int n,m,ans,dft,Cnt,f[N][2],p[N][2],fg[N][2];arr fi,fa,sz,eu,ev,Mi,dfn,vis,mark;
void dfs(int u){
    dfn[u]=++dft;
    go(u)if(v^fa[u]){
        if(!dfn[v])fa[v]=u,dfs(v),sz[u]+=sz[v];
        else{mark[u]=1;
            if(dfn[u]<dfn[v])eu[++Cnt]=u,ev[Cnt]=v;
        }
    }mark[u]|=sz[u]>=2;sz[u]=sz[u]||mark[u];
}
inline int pls(int a,int b){return a+=b,a<P?a:a-P;}
struct Coe{
    int x,y;
    inline Coe operator+(const Coe b){return{pls(x,b.x),pls(y,b.y)};}
    inline Coe operator*(const int b){return{int((ll)x*b%P),int((ll)y*b%P)};}
}k[N][2];
struct Vg{int nx,to;Coe a,b;}E[N];int Fi[N];
inline void ADD(int u,int v,Coe a,Coe b){static int ce=0;E[++ce]={Fi[u],v,a,b},Fi[u]=ce;}
int Vt(int u){
    p[u][0]=p[u][1]=1;vis[u]=1;int pos=0,w;
    go(u)if(!vis[v]){
        w=Vt(v);
        if(!w){
            p[u][1]=(ll)p[u][1]*p[v][0]%P;
            p[u][0]=(ll)p[u][0]*(p[v][0]+p[v][1])%P;
        }else if(mark[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(mark[u])k[u][0]={1,0},k[u][1]={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]=fg[u][1]?0:p[u][0],
    f[u][1]=fg[u][0]?0:p[u][1];
    for(int i=Fi[u],v=E[i].to;i;v=E[i=E[i].nx].to){
        dp(v);int p=f[v][0],q=f[v][1];
        f[u][0]=(ll)f[u][0]*((ll)E[i].a.x*p%P+(ll)E[i].a.y*q%P)%P;
        f[u][1]=(ll)f[u][1]*((ll)E[i].b.x*p%P+(ll)E[i].b.y*q%P)%P;
    }
}
inline void add(int u,int v){static int ce=0;e[++ce]={fi[u],v},fi[u]=ce;}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n),sd(m);int u,v;
    fp(i,1,m)sd(u),sd(v),add(u,v),add(v,u);
    dfs(1);mark[1]=1;
	Vt(1);Mi[1]=1;fp(i,2,Cnt)Mi[i]=Mi[i-1]<<1;
    fp(s,0,(1<<Cnt)-1){
        fp(i,1,Cnt)
            if(s&Mi[i])fg[eu[i]][1]=fg[ev[i]][0]=1;
            else fg[eu[i]][0]=1;
        dp(1);ans=pls(ans,pls(f[1][1],f[1][0]));
        fp(i,1,Cnt)
            if(s&Mi[i])fg[eu[i]][1]=fg[ev[i]][0]=0;
            else fg[eu[i]][0]=0;
    }
    printf("%d\n",ans);
return 0;
}
      • 1

      [HNOI/AHOI2018] 毒瘤

      信息

      ID
      2393
      时间
      1000ms
      内存
      512MiB
      难度
      10
      标签
      递交数
      4
      已通过
      1
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 19ms
      4. Powered by Hydro v5.0.1 Community