PKUSC 2018 随机算法
PKUSC 2018 随机算法
\[ made \ by \ Ameiyo \]
用 $ f[i][s] $ 表示已经有 $ i $ 个点在排列里面,最大独立集的集合为 $ s $ ,这样的方案数。
对于当前不能加入最大独立集的点,在之后仍然不能加入,所以这些点可以被视为相同点,当做消耗品一样使用即可。
而可以加入的点,即加入后会使最大独立集变大的点,就直接放进 $ s $ 就行了。
#include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i, a, b) for (reg int i = (a), i##end = (b); i <= i##end; ++i) #define dep(i, a, b) for (reg int i = (a), i##end = (b); i >= i##end; --i) template <typename _typer> inline _typer read() { _typer init = 0; char ch = getchar(), k = 0; for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-'); for ( ; isdigit(ch); ch = getchar()) init = (init << 3) + (init << 1) + (ch ^ 48); return k ? -init : init; } const ll N = 25, INF = 1e9; const ll M = (1 << 20), Mod = 998244353; int n, m, G[N][N]; int tp[M], mk[N][M]; int f[N][M]; int Pow(int x, int k) { int ans = 1; for ( ; k > 0; x = 1ll * x * x % Mod, k >>= 1) ((k & 1) && (ans = 1ll * ans * x % Mod)); return ans; } void Add(int &x, int y) { ((x += y) >= Mod && (x -= Mod)); } int main() { n = read<int>(), m = read<int>(); rep (i, 0, m - 1) { int x = read<int>() - 1, y = read<int>() - 1; G[x][y] = G[y][x] = true; } rep (i, 0, n - 1) tp[1 << i] = i, mk[i][0] = true; rep (i, 0, n - 1) rep (s, 1, (1 << n) - 1) if (!(s & (1 << i))) mk[i][s] = (mk[i][s & (s - 1)] && !G[i][tp[s & -s]]); f[0][0] = 1; // 不能放的点一直都不能放,所以可以算是一类点,就是把这部分处理掉就行了 rep (i, 0, n - 1) rep (s, 0, (1 << n) - 1) if (f[i][s]) { reg int tmp = f[i][s], res = 0; rep (j, 0, n - 1) if (mk[j][s]) ++res, Add(f[i + 1][s | (1 << j)], tmp); Add(f[i + 1][s], 1ll * tmp * (n - i - res) % Mod); } int Ans = 0, tot = 1, mx = 0; rep (i, 1, n) tot = 1ll * tot * i % Mod; rep (s, 0, (1 << n) - 1) if (f[n][s]) { int cnt = 0; for (int x = s; x > 0; x &= (x - 1)) ++cnt; if (cnt > mx) Ans = f[n][s], mx = cnt; else if (cnt == mx) Add(Ans, f[n][s]); } // cerr << Ans << endl; printf("%lld\n", 1ll * Ans * Pow(tot, Mod - 2) % Mod); return 0; }
注意洛谷上卡内存, $ mk $ 数组开不了,但是 $ O(2 ^ n * n ^ 3) $ 可以过。。。
\[ in \ 2019.12.8 \]
相关推荐
Happyunlimited 2020-04-30
troysps 2020-03-04
风吹夏天 2020-01-24
yedaoxiaodi 2020-01-06
魏莉的微 2019-12-19
baike 2019-12-19
shawsun 2019-12-15
微分 2018-03-02
Qunicy 2019-07-09
郭岚 2019-06-28
YUAN 2019-06-28
ZhuZhuWonder 2019-06-17
MachineIntellect 2015-07-10
蜗牛慢爬的李成广 2019-05-12
StrongHYQ 2018-07-01