loj2540 「PKUWC2018」随机算法 【状压dp】题目链接题解

题目链接

loj2540

题解

有一个朴素三进制状压(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<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#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<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using 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("%lldn",1ll * f[i][maxv] * fv[n] % P);
            break;
        }
    return 0;
}