题目链接

题解

有一个朴素三进制状压\(dp\)，考虑当前点三种状态：没考虑过，被选入集合，被排除

就有了\(O(n3^{n})\)的转移

但这样不优，我们考虑优化状态

设\(f[i][S]\)表示独立集大小为\(i\)，不可选集合为\(S\)【要么是已经在独立集中，要么已经被排除了】

那么剩余点都是可选的

就枚举剩余点\(u\)，记\(u\)相邻的集合为\(S_u\)，那么当\(u\)加入后，集合\(S_u\)的点都不能选，但是由于所有点都会加入排列之中，\(S_u\)中除了\(S\)中的点，剩余点的点会排列在\(u\)之后，那么有

\[f[i + 1][S \cup S_u \cup \{u\}] += A_{n - |S| - 1}^{|S_u| - |S_u \cap S|}f[i][S]\]

复杂度\(O(n^{2}2^{n})\)

但是有很多没用的状态，所以可以过

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
          
           (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
           
            #define LL long long intusing namespace std;const int maxn = 22,maxm = (1 << 21),INF = 1000000000,P = 998244353;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int n,m,G[maxn],f[maxn][maxm],fac[maxn],fv[maxn];inline int qpow(int a,int b){ int re = 1; for (; b; b >>= 1,a = 1ll * a * a % P) if (b & 1) re = 1ll * re * a % P; return re;}inline int cal(int s){ int re = 0; while (s) re += (s & 1),s >>= 1; return re;}inline int A(int n,int m){ return 1ll * fac[n] * fv[n - m] % P;}int main(){ fac[0] = 1; for (int i = 1; i <= 20; i++) fac[i] = 1ll * fac[i - 1] * i % P; fv[20] = qpow(fac[20],P - 2); fv[0] = 1; for (int i = 19; i; i--) fv[i] = 1ll * fv[i + 1] * (i + 1) % P; n = read(); m = read(); int u,v; while (m--){ u = read(),v = read(); G[u] |= (1 << v - 1); G[v] |= (1 << u - 1); } int maxv = (1 << n) - 1; f[0][0] = 1; for (int i = 0; i < n; i++){ for (int s = 0; s <= maxv; s++){ if (!f[i][s]) continue; int tot = cal(s); for (int u = 1; u <= n; u++) if (!(s & (1 << u - 1))){ int siz = cal(G[u]) - cal(s & G[u]),e = s | G[u] | (1 << u - 1); f[i + 1][e] = (f[i + 1][e] + 1ll * f[i][s] * A(n - tot - 1,siz) % P) % P; } } } for (int i = n; i; i--) if (f[i][maxv]){ printf("%lld\n",1ll * f[i][maxv] * fv[n] % P); break; } return 0;}

转载于:https://www.cnblogs.com/Mychael/p/9227904.html

你可能感兴趣的文章