[CQOI2018] 解锁屏幕

Description

给定安卓屏幕上 (n;(nleq 20)) 个点，要求设计解锁图案，连接规则遵循安卓屏幕解锁连接规则，问有多少种解锁图案？

Solution

题外话：今天刷鞋了好爽啊哈哈哈培训有鞋穿了啊哈哈哈

数据范围一眼状压

联想到愤怒的小鸟那题，容易想到定义 (mp[i][j]) 表示在连接 (i,j) 的同时还能连接上哪些中间的点，然后转移的时候或一下就行了。

但是这样会有 (bug)，比如说三个点 ((0,0),(1,1),(2,2)) 实际上从1直接连到3和先连到2再连到3是完全一样的方案，但是统计的时候会统计两遍。

考虑改变 (mp) 数组的定义，(mp[i][j]) 变为要连接 (i,j) 两个点，中间会经过多少点，那么转移的时候我们钦定中间要经过的这些点都必须在之前被连上过，这样转移就不会记重了。

ps：这题据说考试的时候不开O2，尝试卡了一下常，发现 register 真好用，顺便发现 inline 没啥用？

Code

#include<cstdio>
#include<cctype>
#include<cstring>
#define N 21
#define in inline
#define re register
const int mod=100000007;
#define min(A,B) ((A)<(B)?(A):(B))
#define max(A,B) ((A)>(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))

int n;
int ok[N][N];
int mp[N][N];
int x[N],y[N];
int cnt[1<<20];
int f[N][1<<20];

int getint(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}

int M(int &x){
    while(x>=mod) x-=mod;
    while(x<0) x+=mod;
}

signed main(){
    n=getint();
    for(re int i=1;i<=n;i++)
        x[i]=getint(),y[i]=getint();
    int maxn=1<<n;
    for(re int i=0;i<maxn;i++)
        cnt[i]=cnt[i>>1]+(i&1);
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=n;j++){
            if(i==j) continue;
           for(re int k=1;k<=n;k++){
                if(k==i or k==j) continue;
                if((y[j]-y[i])*(x[j]-x[k])==(y[j]-y[k])*(x[j]-x[i])){
                    if(x[k]>max(x[i],x[j]) or x[k]<min(x[i],x[j]) or y[k]>max(y[i],y[j]) or y[k]<min(y[i],y[j]))
                        continue;
                    mp[i][j]|=1<<k-1;
                }
            }
        }
    }
    for(re int i=1;i<=n;i++)
        f[i][1<<i-1]=1;
    for(re int i=0;i<maxn;i++){
        for(re int j=1;j<=n;j++){
            if((i&(1<<j-1))==0) continue;
            if(!f[j][i]) continue;
            for(re int k=1;k<=n;k++){
                if(i&(1<<k-1)) continue;
                if((mp[j][k]&i)!=mp[j][k]) continue;
                M(f[k][i|(1<<k-1)]+=f[j][i]);
                //printf("i=%d,j=%d,k=%d,i|=%d,f=%d,f=%d
",i,j,k,i|mp[j][k],f[j][i],f[k][i|mp[j][k]]);
            }
        }
    } 
    int ans=0;
    for(re int i=0;i<maxn;i++){
        if(cnt[i]>3){
            for(re int j=1;j<=n;j++){
                if(i&(1<<j-1))
                    M(ans+=f[j][i]);
            }
        }
    }
    printf("%d
",ans);/*
    for(int i=0;i<maxn;i++){
        if(cnt[i]<=3) continue;
        printf("
i=%d
",i);
        for(int j=1;j<=n;j++)
            printf("j=%d,f=%d
",j,f[j][i]);
    }*/
    return 0;
}