【洛谷5492】[PKUWC2018] 随机算法（状压DP）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【洛谷5492】[PKUWC2018] 随机算法（状压DP），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2652字，纯文字阅读大概需要4分钟。
内容图文
大致题意： 用随机算法求一张图的最大独立集：每次随机一个排列，从前到后枚举排列中的点，如果当前点加入点集中依然是独立集，就将当前点加入点集中，最终得到的点集就是最大独立集。求这个随机算法的正确率。
前言
\(PKUWC\)的题目就是妙啊。
题目很神仙，但看完题解后就很简单了，可这种东西像我这般蒟蒻根本想不到啊......
状压\(DP\)
设\(f_{i,j}\)表示当前已考虑过点集\(i\)，最大独立集为\(j\)的方案数。
每次我们枚举一个不在点集中的点\(k\)，设与其相邻的点的集合为\(a_k\)。
则，如果我们要选择点\(k\)作为独立集中的点，那么与其相邻的点就不能再选择，方便起见，我们直接把\(a_k\)算作考虑过的点。
即，对于\(f_{i,j}\)和\(k\)，我们可以转移到\(f_{i|2^{k-1}|a_k,j+1}\)。
注，这里之所以是\(2^{k-1}\)，因为我习惯用二进制下第\(x-1\)位来表示第\(x\)个数是否被选择。
不难发现，根据我们的转移方式，由于\(k\)不在点集中，所以点集中被选作独立集中的点的点一定不与\(k\)相邻，否则在那个点被选作独立集中的点时就已经把\(k\)加入点集了，因此必然\(j\)可以加\(1\)。
然后我们考虑，在这一步转移下，\(k\)肯定是要直接加入点集中的，即必然在剩下的点中名列第一，它的位置是固定的。
而对于那些与\(k\)相邻、又不在点集\(i\)中的点（即：\(a_k-(i\&a_k)\)），它们可以在\(k\)之后的任意一个位置（共有\(n-g_i-1\)个位置，其中\(g_i\)代表点集\(i\)中的点，\(1\)代表点\(k\)）加入点集，因此方案数为\(A_{n-g_i-1}^{g_{a_k-(i\& a_k)}}\)。
其中，\(A\)表示排列数，\(A_n^m=\frac{n!}{(n-m)!}\)；\(g_i\)表示点集\(i\)中点的个数。
所以：\(f_{i|2^{k-1}|a_k,j+1}+=f_{i,j}\cdot A_{n-g_i-1}^{g_{a_k-(i\&a_k)}}\)。
由于求概率，而我们求的是方案数，所以最后的答案就是：\(\frac{f_{2^n-1,w}}{n!}\)，其中\(w\)表示最大独立集的大小。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 20
#define X 998244353
#define A(x,y) (1LL*Fac[x]*IFac[(x)-(y)]%X)
using namespace std;
int n,m,a[N+5],f[1<<N][N+5],g[1<<N],Fac[N+5],IFac[N+5];
I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,x,y;for(scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d",&x,&y),a[x]|=1<<y-1,a[y]|=1<<x-1;//读入，记录相邻点
for(Fac[0]=i=1;i<=N;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[N]=Qpow(Fac[N],X-2),i=N-1;~i;--i) IFac[i]=1LL*IFac[i+1]*(i+1)%X;//预处理阶乘逆元
RI j,k,t=1<<n;for(i=0;i^t;++i) g[i]=g[i>>1]+(i&1);for(f[0][0]=1,i=0;i^t;++i)//枚举点集
{
for(j=0;j<=g[i];++j) for(k=1;k<=n;++k) !((i>>k-1)&1)&&//一定要选择不在点集中的点
(f[i|(1<<k-1)|a[k]][j+1]=(1LL*f[i][j]*A(n-g[i]-1,g[a[k]-(i&a[k])])+f[i|(1<<k-1)|a[k]][j+1])%X);//转移
}
for(i=n;!f[t-1][i];--i);return printf("%d",1LL*f[t-1][i]*IFac[n]%X),0;//求最大独立集点数，然后输出答案
}内容总结
以上是互联网集市为您收集整理的【洛谷5492】[PKUWC2018] 随机算法（状压DP）全部内容，希望文章能够帮你解决【洛谷5492】[PKUWC2018] 随机算法（状压DP）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。