BZOJ 5299: [Cqoi2018]解锁屏幕
2024-09-29 17:16:40
状压DP
#include<cstdio>
using namespace std;
const int mod=1e8+7;
int F[1000005][25],dis[25][25],lim[1000005];
struct node{
int x,y;
}E[25];
int main(){
int n;
scanf("%d",&n);
for (int i=0; i<n; i++) scanf("%d%d",&E[i].x,&E[i].y);
for (int S=0; S<n; S++)
for (int T=S+1; T<n; T++)
for (int k=0; k<n; k++){
if (k==S || k==T) continue;
int x=E[S].x-E[k].x,y=E[S].y-E[k].y;
int X=E[T].x-E[k].x,Y=E[T].y-E[k].y;
if (X*y==x*Y) {
if (E[k].x>E[S].x && E[k].x>E[T].x) continue;
if (E[k].x<E[S].x && E[k].x<E[T].x) continue;
if (E[k].y>E[S].y && E[k].y>E[T].y) continue;
if (E[k].y<E[S].y && E[k].y<E[T].y) continue;
dis[S][T]|=(1<<k);
dis[T][S]|=(1<<k);
}
}
for (int i=0; i<n; i++) F[1<<i][i]=1;
for (int i=1; i<(1<<n); i++) lim[i]=lim[i>>1]+(i&1);
for (int i=0; i<(1<<n); i++)
for (int S=0; S<n; S++)
if (F[i][S]){
for (int T=0; T<n; T++)
if (!(i&(1<<T)) && (i&dis[S][T])==dis[S][T]) (F[i|(1<<T)][T]+=F[i][S])%=mod;
}
int ans=0;
for (int i=0; i<(1<<n); i++)
for (int S=0; S<n; S++)
if (lim[i]>=4) (ans+=F[i][S])%=mod;
printf("%d\n",ans);
return 0;
}
最新文章
- 在Azure虚拟机上安装VNC
- Unity自动寻路入门指南
- 解决点击cell时,UILabel的背景颜色消失的问题
- 《奥威Power-BI案例应用:带着漫画看报告》腾讯课程开课啦
- jQuery EasyUI教程之datagrid应用(二)
- git基本技巧及进阶
- modelsim操作流程
- (C语言)数组与指针的区别
- JS网页顶部弹出可关闭广告图层
- 怎样修改 Openstack Horizon(Dashboard)的显示界面 (一)
- Eclipse卡死问题解决办法
- PADS Logic 常见错误报告内容
- SSL 通信原理及Tomcat SSL 配置
- PHP MySQL 连接数据库 之 Connect
- 如果nginx 中worker_connections 值设置是1024,worker_processes 值设置是4,按反向代理模式下最大连接数的理论计算公式: 最大连接数 = worker_processes * worker_connections/4
- mysql无法输入中文
- HY.Mail:C#简单、易用的邮件工具库
- django settings多环境配置
- VIsual Studio编译OpenCV:无法打开python27_d.lib(python36_d.lib)的问题
- alibaba的FastJson(高性能JSON开发包) json转换