「PKUWC 2018」随机算法 (60分部分分做法)
2024-10-19 16:34:19
明天就是CTSC的DAY 2了qwq,晚上敲敲暴力攒攒RP,果断随便看了个题就是打暴力hhhhh
前50% O(3^N) 暴力没什么好说的,我们设F[S][s]为已经选了S集合中的点,并且这个集合中的点的最大独立集是s的方案数,最后统计完了乘上 n! 的逆元就好了。 (s肯定是S的一个子集,所以复杂度是 3^n)
然鹅中间的暴力分只会链。。。。。
首先如果n是奇数的话,那么最大独立集只可能是所有奇数点,所有这种情况下我们知道了选了的点的集合就知道独立集是什么了,所以可以直接 O(2^n) dp了。。。。
但是出题人并没有这么良心2333,这一个点的n在最后的数据里是偶数。。。。
考虑如果n是偶数的情况的话,独立集只可能是:全是奇数的点 或者 全是偶数的点 或者 ∑ [i是偶数] <=i的全是奇数的点 和 >i的全是偶数的点,这样的话我们先用 与求n是奇数的同样的方法 (钦定最大独立集是所有奇数点) 求出对于每个偶数i,最大独立集是<=i的奇数的点的答案,然后卷积合并一下就好啦,因为后面的全是偶数的点的集合可以看成是反向的全是奇数的点的集合。
合并的时候还要乘上一个组合数,因为两边元素之间的顺序还没有确定、
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=300005,ha=998244353;
inline int add(int &x,int y){ x+=y; if(x>=ha) x-=ha;}
inline int ksm(int x,int y){ int an=1; for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha; return an;}
unordered_map<int,int> f[maxn];
unordered_map<int,int>:: iterator it;
int n,ci[35],m,uu,vv,BC[maxn],ans,M;
bool G[35][35],can[maxn][23];
inline int ADD(int S,int x){ return can[S][x]?(S|ci[x]):S;}
int g[maxn*4+5],jc[233],C[233][233]; inline void init(){
for(int i=0;i<ci[n];i++)
for(int j=0;j<n;j++) if(!(ci[j]&i)){
can[i][j]=1;
for(int o=0;o<n;o++) if((ci[o]&i)&&G[o][j]){
can[i][j]=0;
break;
} }
} inline void calc(){
ans=ans*(ll)ksm(jc[n],ha-2)%ha;
} inline void solve(){
f[0][0]=1; int all=ci[n]-1; for(int i=0;i<all;i++)
for(it=f[i].begin();it!=f[i].end();++it)
for(int j=0,S,to;j<n;j++) if(!(ci[j]&i)){
S=i|ci[j],to=ADD(it->first,j),M=max(M,BC[to]);
add(f[S][to],it->second);
} for(it=f[all].begin();it!=f[all].end();++it) if(BC[it->first]==M) add(ans,it->second);
} inline int get_line(int N){
memset(g,0,sizeof(g));
g[0]=1; int all=ci[N]-1; for(int i=0;i<all;i++) if(g[i])
for(int j=0;j<N;j++) if(!(ci[j]&i)){
if((j&1)&&!((i&ci[j-1])||(i&ci[j+1]))) continue; add(g[i|ci[j]],g[i]);
}
return g[all];
} inline void qwqwq(){
int o[23];
for(int i=2;i<=n;i+=2) o[i]=get_line(i);
add(ans,o[n]),add(ans,o[n]); for(int i=2;i<n;i+=2) add(ans,o[i]*(ll)o[n-i]%ha*C[n][i]%ha);
} int main(){
ci[0]=1;
for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;
jc[0]=1;
for(int i=1;i<=20;i++) jc[i]=jc[i-1]*(ll)i%ha;
C[0][0]=1;
for(int i=1;i<=75;i++){
C[i][0]=1;
for(int j=1;j<=i;j++) add(C[i][j],C[i-1][j-1]),add(C[i][j],C[i-1][j]);
} scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&uu,&vv),G[uu-1][vv-1]=G[vv-1][uu-1]=1; if(n<=17){
for(int i=1;i<ci[n];i++) BC[i]=BC[i^(i&-i)]+1;
init(),solve();
}
else if(n&1) ans=get_line(n);
else qwqwq(); calc(); printf("%d\n",ans);
return 0;
}
最新文章
- java.lang.IllegalStateException: Cannot add header view to list -- setAdapter has already been called.
- 设置hr标签的粗细
- Cocoapods的安装,卸载和使用
- TFS简介
- HDU 1875 畅通工程再续 (最小生成树)
- [转贴] C/C++中动态链接库的创建和调用
- C# WinForm窗体界面设置问题
- win10常见问题-任务栏消失
- -_-#【jsonp】cache
- Hadoop学习笔记(2)hadoop框架解析
- Ibatis2.3.4的一个bug
- ubuntu14.04中 gedit 凝视能显示中文,而source insight中显示为乱码的解决的方法
- VS2015在对GIT的支持
- 【转】linux建立软链接
- LNMP 快速安装
- Spring JdbcTemplate用法整理
- ABP官方文档翻译 6.4 导航
- qduoj前端二次开发简略流程
- Ganglia监控扩展实现机制
- Spring Boot到底是怎么运行的,你知道吗?
热门文章
- SQLite3中dos命令下退出";...>;";状态的方法
- Oracle数据库存量数据抽取使用spool控制命令
- 训练caffe:registry.count(type) == 0 (1 vs. 0) Solver type Nesterov already registered
- 再看数据库——(5)Group By与Order By
- 【bzoj1270】[BeijingWc2008]雷涛的小猫 dp
- 【CZY选讲&#183;棋盘迷宫】
- org.apache.catalina.core.StandardWrapperValve.invoke Servlet.service() for servlet [WebApp] in context with path关于数据库库的问题
- delete zone and cfgsave on brocade by CMD
- log4net日志分割,按大小分割
- PHP会话控制