loj2540. 「PKUWC2018」随机算法

题意

略。

题解

这道题的状态还是挺难找的。
初始排列为空。考虑设\(f_{s, i}\)表示当前状态，独立集为\(s\)，已经不在独立集里面（即与\(s\)中的点有连边）且还没有加入排列的点数为\(i\)。
则有初始状态\(f_{0, 0} = 1\)。
考虑转移，如果某一个点可以加入这个独立集，则：
\[f_{s \cup \{x\}, i + \text{new}(x, s)} += f_{s, i} \ (x \notin s)\]
其中\(new(x, s)\)代表的是与\(x\)有连边，并且不属于\(s\)且不与\(s\)中任何点有连边的点的个数。
这个操作代表将\(x\)加入排列。
只有这样一种操作是不够的，考虑要把已经不在独立集里面且还没有加入排列的点加入排列，如果有\(i\)个这样的点，那么这次可以选择任何一个加入。
即
\[f_{s, i - 1} += f_{s, i}\]
考虑到转移一定构成了一个DAG（先按集合\(s\)的偏序，再按点数\(i\)的偏序），所以是没问题的。
复杂度\(\mathcal O(2 ^ n n ^ 2)\)。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int N = 20, M = 1 << 20, mod = 998244353;
int n, m, c, ans, e[M], d[N][M], t[M], f[N][M];
int power (int x, int y) {
    int ret = 1;
    for ( ; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) {
            ret = 1ll * ret * x % mod;
        }
    }
    return ret;
}
void U (int &x, int y) {
    if ((x += y) >= mod) {
        x -= mod;
    }
}
int main () {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        e[1 << i] = 1 << i;
    }
    for (int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y, --x, --y;
        e[1 << x] |= 1 << y, e[1 << y] |= 1 << x;
    }
    m = 1 << n;
    for (int i = 0; i < n; ++i) {
        for (int s = 0; s < m; ++s) {
            if (s >> i & 1) {
                e[s] |= e[s ^ 1 << i];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int s = 0; s < m; ++s) {
            if (~e[s] >> i & 1) {
                d[i][s] = __builtin_popcount(e[s] | e[1 << i] ^ (1 << i)) - __builtin_popcount(e[s]);
            }
        }
    }
    f[0][0] = 1;
    for (int s = 0; s < m; ++s) {
        for (int i = n; i; --i) {
            U(f[i - 1][s], 1ll * f[i][s] * i % mod);
        }
        for (int i = n; ~i; --i) {
            if (f[i][s]) {
                for (int x = 0; x < n; ++x) {
                    if (~e[s] >> x & 1) {
                        U(f[i + d[x][s]][s | 1 << x], f[i][s]);
                    }
                }
            }
        }
    }
    for (int s = 0; s < m; ++s) {
        if (f[0][s]) {
            if (__builtin_popcount(s) > c) {
                c = __builtin_popcount(s), ans = 0;
            }
            if (__builtin_popcount(s) == c) {
                U(ans, f[0][s]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans = 1ll * ans * power(i, mod - 2) % mod;
    }
    cout << ans << endl;
    return 0;
}