sdwc2019 可爱的Mys_C_K小学妹的爆裂摧毁好题

题意 : \(n\)个点m条边的无向连通图dfs序计数, 对\(998244343\)取模。 \(n\leq18,m\leq n*(n-1)/2\)

显然是状压, 但是状态设计比较困难, 因为受到回溯的影响。

考虑一个比较靠谱的状态:\(f[S][j]\)定义为当前已走状态为\(S\), 位于点\(j\),从点\(j\)出发不经过已走点,走出极大连通子图的方案数。

假设\(P\)为与\(j\)有直接相连的边且已走的点集, 那\(f[S][j]\)就是断掉\(P\)点集与\(j\)的边然后再炸掉\(j\)以后分裂出的连通子图的方案数。

定义\(cc[S][j]\)为炸掉\(S\)后从点\(j\)走出的极大连通子图

容易得到状态转移方程 :

\(f[S][i]=\begin{cases} \sum_{j\notin S}{f[S|cc[S][j]][i]*f[S|(1\ll(j-1))][j]},~S\neq\emptyset ;\\ 1,S=\emptyset ; \end{cases}\)

其实就是连通分量内部如何走

#include<cstdio>

const int N = 19;
const int p = 998244353;
typedef long long ll;
ll f[1 << N][N], cc[1 << N][N];
int d[N][N], n, m, up;

inline void fcc (int s, int x, int &mask) {
    mask |= (1 << (x - 1)); 
    for (int i = 1; i <= n; i++) if (d[x][i] && (!((1 << i) & s))) fcc (s, i, mask);
}
int main () {
    scanf ("%d%d", &n, &m); 
    while (m--) {
      int x, y; scanf ("%d%d", &x, &y), d[x][y] = d[y][x] = 1;
    } up = (1 << n) - 1;
    for (int S = up; S > 0; S--) for (int i = 1; i <= n; i++) 
      if (((1 << (i - 1)) & S) > 0) { int flag = 1; 
        for (int j = 1; j <= n; j++) if (d[i][j] && !((1 << (j - 1)) & S)) {
          if (!cc[S][j]) fcc (S, j, cc[S][j]);
            f[S][i] = (f[S][i] + f[S | cc[S][j]][i] * f[S | (1 << (j - 1))][j]) % p;
            flag = 0;
          } f[S][i] += flag;
        } 
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + f[1 << (i - 1)][i]) % p;
    printf ("%lld\n", ans % p); 
return 0;
}

sdwc2019 可爱的Mys_C_K小学妹的爆裂摧毁好题

原文：https://www.cnblogs.com/cjc030205/p/11638108.html