M_sea

洛谷4426 [HNOI2018]毒瘤
LuoguBZOJ分析先把题意转化一下:给定一张有最多$11$条非树边的图,求独立集的方案数。如果是一棵树设$f[...
扫描右侧二维码阅读全文
02
2019/01

洛谷4426 [HNOI2018]毒瘤

Luogu

BZOJ

分析

先把题意转化一下:给定一张有最多$11$条非树边的图,求独立集的方案数。

如果是一棵树

设$f[i][0/1]$表示以$i$为根的子树,$i$选/不选的方案数。

显然有:

$\large f[i][0]=\sum\limits_{v\in Son_i}(f[v][0]+f[v][1])$

$\large f[i][1]=\sum\limits_{v\in Son_i}f[v][0]$

暴力DP即可。

非树边怎么办

考虑暴力怎么写:枚举每条非树边连接的两个端点选还是不选。

显然只有三种情况:$(0,0)$、$(0,1)$、$(1,0)$,然而可以只枚举上面的点选还是不选,也就是可以把$(0,0)$和$(0,1)$放到一起。

对于枚举出的每一个状态,再暴力跑一遍DP。

时间复杂度$O(2^{11}n)$,可以收获$75pt$的好成绩。

继续优化

发现每次受到影响的点很少,考虑把这些点抽出来建虚树。

发现,虚树上$u$转移到它的父节点$f$时,$f$的dp值是和$u$的dp值成正比的,而这个系数是可以dp出来的。

所以建虚树的时候顺便搞出这个系数,然后就可以愉悦地在虚树上跑$\mathrm{DP}$了。

所以为什么这25pt这么难写啊

代码

比较杂乱就是了。。。

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXM=MAXN+10;
const int MOD=998244353;

struct Edge { int v,nxt; };
Edge e[MAXM<<1];
int head[MAXN];
int n,m;
int dfn[MAXN],dfs_clock=0;
int eu[MAXN],ev[MAXN],cnt=0;
int f[MAXN][2],fg[MAXN][2];
int in[MAXN],sz[MAXN];
int vis[MAXN];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;    
}

inline void dfs(int u,int fa) {
    dfn[u]=++dfs_clock;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        if (!dfn[v]) dfs(v,u),sz[u]+=sz[v];
        else {
            in[u]=1;
            if (dfn[u]<dfn[v]) eu[++cnt]=u,ev[cnt]=v;
        }
    }
    if (sz[u]>=2) in[u]=1;
    sz[u]=sz[u]||in[u];
}

struct Coe { //虚树上边的系数
    int x,y;
    Coe(int x_=0,int y_=0) { this->x=x_,this->y=y_; }
    Coe operator +(const Coe b) { return Coe(x+b.x,y+b.y); }
    Coe operator *(const int b) { return Coe(1ll*x*b%MOD,1ll*y*b%MOD); }
} k[MAXN][2];

struct vEdge { int v,nxt; Coe a,b; };
vEdge ve[MAXM];
int vhead[MAXN];
int p[MAXN][2];

inline void vaddEdge(int u,int v,Coe a,Coe b) {
    static int vcnt=0;
    ve[++vcnt].v=v,ve[vcnt].nxt=vhead[u],ve[vcnt].a=a,ve[vcnt].b=b;
    vhead[u]=vcnt;
}

inline int build(int u) { //建虚树
    p[u][0]=p[u][1]=1,vis[u]=1; int pos=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]) continue;
        int w=build(v);
        if (!w) {
            p[u][0]=1ll*p[u][0]*(p[v][0]+p[v][1])%MOD;
            p[u][1]=1ll*p[u][1]*p[v][0]%MOD;
        }
        else if (in[u]) vaddEdge(u,w,k[v][0]+k[v][1],k[v][0]);
        else k[u][0]=k[v][0]+k[v][1],k[u][1]=k[v][0],pos=w;
    }
    if (in[u]) k[u][0]=(Coe){1,0},k[u][1]=(Coe){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;
}

inline 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 (re int i=vhead[u];i;i=ve[i].nxt) {
        int v=ve[i].v;
        dp(v); Coe a=ve[i].a,b=ve[i].b;
        f[u][0]=1ll*f[u][0]*(1ll*a.x*f[v][0]%MOD+1ll*a.y*f[v][1]%MOD)%MOD;
        f[u][1]=1ll*f[u][1]*(1ll*b.x*f[v][0]%MOD+1ll*b.y*f[v][1]%MOD)%MOD;
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1,u,v;i<=m;++i) {
        u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,0);
    in[1]=1; build(1);
    int ans=0;
    for (re int S=0;S<(1<<cnt);++S) { //枚举非树边的状态
        for (re int i=1;i<=cnt;++i) {
            if (S&(1<<(i-1))) fg[eu[i]][1]=fg[ev[i]][0]=1;
            else fg[eu[i]][0]=1;
        }
        dp(1);
        ans=(ans+(f[1][1]+f[1][0])%MOD)%MOD;
        memset(fg,0,sizeof(fg));
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 56 PM

4 条评论

  1. water_mi

    您太强了

    1. M_sea
      @water_mi

  2. smy

    好fAKe啊

    1. M_sea
      @smy

      哪里fAKe了啊qwq

发表评论