LOJ2540「PKUWC2018」随机算法
2024-09-05 14:21:06
又是一道被咕了很久的题 貌似从WC2019之前咕到了现在
我们用f[i][s]表示现在最大独立集的大小为i 不可选集合为s
然后转移O(n)枚举加进来的点就比较简单啦
这个的复杂度是O(2^n*n^2)
据说有更科学的O(2^n*n)
但是显然这个做法就能过了(
详情参见PKUWC2019D1T1(大雾
代码扔这里了。
//Love and Freedom.
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define ll long long
#define inf 20021225
#define mdn 998244353
#define N 21
using namespace std;
int read()
{
int s=,f=; char ch=getchar();
while(ch<'' || ch>'') {if(ch=='-') f=-;ch=getchar();}
while(ch>='' && ch<='') s=s*+ch-'',ch=getchar();
return f*s;
}
int ksm(int bs,int mi)
{
int ans=;
while(mi)
{
if(mi&) ans=1ll*ans*bs%mdn;
bs=1ll*bs*bs%mdn; mi>>=;
}
return ans;
}
int f[N][<<N],fac[N],inv[N],cnt[<<N],n,w[N];
void add(int x,int y)
{
w[x]|=<<y; w[y]|=<<x;
}
int A(int n,int m)
{
if(n<m) return ;
return 1ll*fac[n]*inv[n-m]%mdn;
}
void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;}
int main()
{
n=read(); int m=read(); fac[]=; int x,y;
for(int i=;i<=n;i++) fac[i]=1ll*fac[i-]*i%mdn;
inv[n]=ksm(fac[n],mdn-);
for(int i=n;i;i--) inv[i-]=1ll*inv[i]*i%mdn;
for(int i=;i<=m;i++) x=read(),y=read(),add(x-,y-);
for(int i=;i<n;i++) w[i]|=<<i;
f[][]=; int top=<<n;
for(int i=;i<top;i++) cnt[i]=cnt[i>>]+(i&);
for(int i=;i<n;i++) for(int s=;s<top;s++)
if(f[i][s]) for(int j=;j<n;j++) if(!((s>>j)&))
upd(f[i+][s|w[j]],1ll*f[i][s]*A(n-cnt[s]-,cnt[w[j]-(w[j]&s)]-)%mdn);
for(int i=n;i;i--) if(f[i][top-])
{
printf("%d\n",1ll*f[i][top-]*inv[n]%mdn);
break;
}
return ;
}
最新文章
- C语言 02 include
- miniui
- 从源代码的角度聊聊java中StringBuffer、StringBuilder、String中的字符串拼接
- mysql启动不成功显示The server quit without updating PID file的解决方法
- codeforces 483C.Diverse Permutation 解题报告
- Janus WinForms Controls
- AR 应收 表
- 502 Proxy Error The proxy server received an invalid response from an upstream server
- Android NDK R9d 安装
- PHP 5 数据类型
- 比较实用的webpack配置代码
- zabbix自动截图留档_python版
- Postgresql 启动could not create listen socket for ";localhost";错误的解决
- 安装scala
- 使用guava过期map
- MYSQL之IFNULL
- FP ABPPMGR表 其它常用存储过程
- C/C++掌握技能(一)
- GAN初步——本质上就是在做优化,对于生成器传给辨别器的生成图片,生成器希望辨别器打上标签 1,体现在loss上!
- C#基础第五天-作业-用DataTable制作名片集