首页 / 算法 / PKUSC 2018 随机算法
PKUSC 2018 随机算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了PKUSC 2018 随机算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2221字,纯文字阅读大概需要4分钟。
内容图文
![PKUSC 2018 随机算法](/upload/InfoBanner/zyjiaocheng/653/4c5a7f3cb51f42f8ad1bd7cb73790684.jpg)
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 \]
内容总结
以上是互联网集市为您收集整理的PKUSC 2018 随机算法全部内容,希望文章能够帮你解决PKUSC 2018 随机算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。