[PKUWC 2018]随机算法
2024-10-11 16:52:28
Description
给定一张有 \(n\) 个点 \(m\) 条边的无向图,生成 \(1\sim n\) 的全排列,假设一个排列是 \(p\) , \(S\) 是当前最大独立集;如果 \(S\cup {p_i}\) 是独立集就令 \(S=S\cup {p_i}\) ;
求这 \(n!\) 个独立集为最大独立集的概率,答案对 \(998244353\) 取模。
\(1\leq n\leq 20\)
Solution
我们记 \(mx_{i,j}\) 表示排好序的点以及这些点周围的的点的状态为 \(i\) ,有 \(j\) 个点还未选入序列,其中的最大独立集内点数最大值; \(f_{i,j}\) 表示该状态下的排列个数。
转移就是考虑这一位是将状态内的未选择的点排入排列内或者是重新在状态外再选点。
时间复杂度是 \(O(2^n\times n^2)\) ,并不满。
Code
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N = 20+5, SIZE = (1<<20)+5, yzh = 998244353;
int n, m, u, v, sta[N], bin[N], f[SIZE][N], mx[SIZE][N], cnt[SIZE], inv[N];
void work() {
scanf("%d%d", &n, &m); bin[0] = inv[1]= 1;
for (int i = 1; i <= n; i++) bin[i] = bin[i-1]<<1;
for (int i = 2; i <= n; i++) inv[i] = -1ll*yzh/i*inv[yzh%i]%yzh;
for (int i = 1; i <= bin[n]; i++) cnt[i] = cnt[i-lowbit(i)]+1;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
sta[u-1] |= bin[v-1]; sta[v-1] |= bin[u-1];
}
f[0][0] = 1;
for (int i = 0; i < bin[n]; i++)
for (int j = n; j >= 0; j--)
if (f[i][j]) {
if (j) {
if (mx[i][j-1] == mx[i][j]) (f[i][j-1] += 1ll*f[i][j]*j%yzh) %= yzh;
else if (mx[i][j-1] < mx[i][j]) mx[i][j-1] = mx[i][j], f[i][j-1] = 1ll*f[i][j]*j%yzh;
}
for (int k = 0; k < n; k++)
if (!(bin[k]&i)) {
int S = (i|sta[k]|bin[k]), t = cnt[sta[k]]-cnt[sta[k]&i];
if (mx[S][j+t] < mx[i][j]+1) mx[S][j+t] = mx[i][j]+1, f[S][j+t] = f[i][j];
else if (mx[S][j+t] == mx[i][j]+1) (f[S][j+t] += f[i][j]) %= yzh;
}
}
int ans = f[bin[n]-1][0];
for (int i = 1; i <= n; i++) ans = 1ll*ans*inv[i]%yzh;
printf("%d\n", (ans+yzh)%yzh);
}
int main() {work(); return 0; }
最新文章
- window下 配置gitlab ssh非端口22端口
- JavaScript的事件绑定及深入
- Microsoft Power BI Designer
- C++中不可重载的5个运算符
- An unspecified error occurred!
- BZOJ 2301 Problem B(莫比乌斯反演)
- 文件下载Demo
- fragment的切换
- Top 10 Books For Advanced Level Java Developers
- js验证是否为数字的总结(转)
- JDK8 指南(译)
- xxxx-xx-xx的时间的加减
- 8、TypeScript-解构赋值
- linux 平台core dump文件生成
- vue.js在visual studio 2017下的安装
- sitecore系列教程之简单和个性化
- 基础回顾—list遍历4种
- insert NULL into mysql
- AME_Oracle自带AME审批链详解AME Standard Handler(概念)
- BleedTree动画混合树