一道毒瘤的 状态压缩 DP 题。

题目链接：Luogu P4460/LibreOJ 2536/BZOJ 5299/CQOI 2018 D2T1。

题目

题目描述

自己去看。

题解

思路

观察到 $n$ 比较小，考虑 状态压缩 DP。

设 $\text{dp} _ {S,i}$ 表示二进制下选取的点的状态 $S$，以及最后一个点的编号为 $i$，得到路径的条数，那么我们有状态转移方程：

$$\text{dp} _ {S,i}=\sum _ {j \in S , (i,j) \text{不被阻挡} } \text{dp} _ {S-j,j}$$

记得提前预处理会不会被阻挡。

另外提醒本题模数是 $10^8+7$，不要打错了。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define MOD 100000007 //注意模数是 1e8+7
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool cnt=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)cnt|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return cnt?-res:res;
}

const int MAXN=20;

int n;

struct Point{
    int x,y;
    inline void Read(void){
        x=read(),y=read();
        return;
    }
};

int R[MAXN][MAXN];
int dp[1<<MAXN][MAXN];
int cnt[1<<MAXN]; //cnt[i] 表示 i 的二进制表示下 1 的个数
Point p[MAXN];

inline bool check(const Point& l,const Point& mid,const Point& r){ //判断 l 到 r 的路径是否被 mid 阻挡
    return ((r.x-l.x)*(mid.y-l.y)==(r.y-l.y)*(mid.x-l.x))&&((mid.x-l.x)*(mid.x-r.x)<0||(mid.y-l.y)*(mid.y-r.y)<0);
}

int main(void){
    n=read();
    for(reg int i=0;i<n;++i)
        p[i].Read();
    for(reg int i=1;i<(1<<n);++i)
        cnt[i]=cnt[i>>1]+(i&1); //统计 1 的个数
    for(reg int i=0;i<n;++i)
        for(reg int j=0;j<n;++j)
            if(i!=j)
                for(reg int k=0;k<n;++k)
                    if(k!=i&&k!=j)
                        if(check(p[i],p[k],p[j]))
                            R[i][j]|=(1<<k); //从 i 到 j 会被 k 阻挡
    for(reg int i=0;i<n;++i)
        dp[1<<i][i]=1; //临界状态
    reg int ans=0;
    for(reg int S=1;S<(1<<n);++S){
        for(reg int j=0;j<n;++j)
            if(dp[S][j]&&((S>>j)&1)){
                if(cnt[S]>=4)
                    ans=(ans+dp[S][j])%MOD;
                for(reg int k=0;k<n;++k)
                    if(((S>>k)&1)||(R[j][k]&S)!=R[j][k])
                        continue; //如果 S 里面选了 k 或者 j 到 k 被阻挡，则跳过
                    else
                        dp[S|(1<<k)][k]=(dp[S|(1<<k)][k]+dp[S][j])%MOD;
            }
    }
    printf("%d\n",ans); //输出答案
    return 0;
}