不想打虚树发现可以 ddp 做 x

Problem

给你一棵树，最多多放 11 条边，问独立集方案数。

Solution

假设一棵树的话 dp 方程很简单。
子树情况相加，合并时相乘。

然后像 ddp 模板那样把矩阵和转移顺序改写一下。

但是这样做有个问题，就是轻链向上跳时可能乘除零。

解决方案见这里：
https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4426

差点绝望的时候看到这里还是很开心的 ww

Code

// Code by ajcxsu
// Problem: duliu

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
#define MOD (998244353)
using namespace std;

const int N=1e5+10, M=3e5+10;
typedef long long ll;
template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}
inline int qpow(int x, int y) {
    int ret=1;
    while(y) {
        if(y&1) ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD, y>>=1;
    }
    return ret;
}
inline int inv(int x) { return qpow(x%MOD, MOD-2); }

int h[N], to[M], nexp[M], p=2;
char del[M];
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
vector<int> aga[N];
#define mea N
#define qua N
int nd[100], eid;
char li[N];

int dep[N], dfn[N], fa[N], siz[N], top[N], son[N], bot[N], idx;
int xmea[N];
int dp[N][2], ddp[N][2], xqua[N][2];
void ad(int x, int y, int z) {
    ddp[x][y]=1ll*ddp[x][y]*((z)?z:1)%MOD; xqua[x][y]+=(z==0);
}
void de(int x, int y, int z) {
    ddp[x][y]=1ll*ddp[x][y]*((z)?inv(z):1)%MOD; xqua[x][y]-=(z==0);
}
void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            fa[to[u]]=x, dfs1(to[u], k+1);
            siz[x]+=siz[to[u]]; if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
        }
        else if(to[u]!=fa[x])
            aga[x].push_back(to[u]), aga[to[u]].push_back(x), 
            del[u]=del[u^1]=1, nd[eid++]=x, nd[eid++]=to[u];
    return;
}
void dfs2(int x, int t) {
    top[x]=t, dfn[x]=++idx, xmea[idx]=x;
    dp[x][0]=dp[x][1]=ddp[x][0]=ddp[x][1]=1;
    if(son[x]) {
        dfs2(son[x], t), bot[x]=bot[son[x]];
        dp[x][0]=1ll*dp[x][0]*(dp[son[x]][0]+dp[son[x]][1])%MOD;
        dp[x][1]=1ll*dp[x][1]*dp[son[x]][0]%MOD;
    }
    else bot[x]=x;
    for(int u=h[x];u;u=nexp[u]) if(!del[u] && !dfn[to[u]]) {
        dfs2(to[u], to[u]);
        dp[x][0]=1ll*dp[x][0]*(dp[to[u]][0]+dp[to[u]][1])%MOD;
        dp[x][1]=1ll*dp[x][1]*dp[to[u]][0]%MOD;
        ddp[x][0]=1ll*ddp[x][0]*(dp[to[u]][0]+dp[to[u]][1])%MOD;
        ddp[x][1]=1ll*ddp[x][1]*dp[to[u]][0]%MOD;
    }
}

struct matrix {
    static const int N=2;
    int a[mea][qua];
    matrix() { CLR(a, 0); }
    int* operator [] (int x) { return a[x]; }
    matrix operator * (matrix b) {
        matrix c;
        for(int i=0;i<N;i++)
        for(int k=0;k<N;k++)
        for(int j=0;j<N;j++)
            c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%MOD;
        return c;
    }
    int val() { return (a[0][0]+a[1][0])%MOD; }
} s[N<<2];
#define ls x<<1
#define rs x<<1|1
void build(int x, int l, int r) {
    if(l==r) {
        s[x][0][0]=s[x][0][1]=(xqua[xmea[l]][0]?0:ddp[xmea[l]][0]), 
        s[x][1][0]=(xqua[xmea[l]][1]?0:ddp[xmea[l]][1]); 
        return;
    }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    s[x]=s[ls]*s[rs];
}
void updata(int x, int l, int r, int d) {
    if(l==r) {
        s[x][0][0]=s[x][0][1]=(xqua[xmea[l]][0]?0:ddp[xmea[l]][0]), 
        s[x][1][0]=(xqua[xmea[l]][1]?0:ddp[xmea[l]][1]); 
        return;
    }
    int mid=(l+r)>>1;
    if(d<=mid) updata(ls, l, mid, d);
    else updata(rs, mid+1, r, d);
    s[x]=s[ls]*s[rs];
}
matrix query(int x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return s[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return query(ls, l, mid, xl, xr);
    else if(xl>mid) return query(rs, mid+1, r, xl, xr);
    else return query(ls, l, mid, xl, mid) * query(rs, mid+1, r, mid+1, xr);
}

int n, m;
void modify(int x, int v1, int v2) {
    ddp[x][0]=v1, ddp[x][1]=v2;
    int k;
    matrix na;
    while(k=fa[top[x]]) {
        na=query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
        de(k, 0, na[0][0]+na[1][0]);
        de(k, 1, na[0][0]);
        updata(1, 1, n, dfn[x]), na=query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
        ad(k, 0, na[0][0]+na[1][0]);
        ad(k, 1, na[0][0]);
        x=k;
    }
    updata(1, 1, n, dfn[x]);
}

int ans;
void dfs(int x) {
    if(x==eid) { ans=(ans+query(1, 1, n, dfn[1], dfn[bot[1]]).val())%MOD; return; }
    int r1, r2;
    bool c=1;
    r1=ddp[nd[x]][0], r2=ddp[nd[x]][1];
    for(int na:aga[nd[x]]) if(li[na] || na==nd[x]) c=0;
    
    // 0
    li[nd[x]]=0, modify(nd[x], r1, 0);
    dfs(x+1);
    modify(nd[x], r1, r2);
    // 1
    if(c) {
        li[nd[x]]=1, modify(nd[x], 0, r2);
        dfs(x+1);
        li[nd[x]]=0, modify(nd[x], r1, r2);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>m;
    int u, v;
    for(int i=0;i<m;i++) cin>>u>>v, ins(u, v), ins(v, u);
    dfs1(1, 1), dfs2(1, 1), build(1, 1, n);
    sort(nd, nd+eid), eid=unique(nd, nd+eid)-nd;
    dfs(0);
    cout<<ans<<'\n';
    return 0;
}