【BZOJ5299】【CQOI2018】解锁屏幕（动态规划，状态压缩）

题面

BZOJ

洛谷

Description

使用过Android手机的同学一定对手势解锁屏幕不陌生。Android的解锁屏幕由3x3个点组成，手指在屏幕上画一条

线将其中一些点连接起来，即可构成一个解锁图案。如下面三个例子所示：

画线时还需要遵循一些规则

1．连接的点数不能少于4个。也就是说只连接两个点或者三个点会提示错误。

2．两个点之间的连线不能弯曲。

3．每个点只能"使用"一次，不可重复。这里的"使用"是指手指划过一个点，该点变绿。

4．两个点之间的连线不能"跨过"另一个点，除非那个点之前已经被"使用"过了。

对于最后一条规则，参见下图的解释。左边两幅图违反了该规则：而右边两幅图(分别为2→4→1→3→6和→5→4→1→9→2)

则没有违反规则，因为在"跨过"点时，点已经被"使用"过了。

现在工程师希望改进解锁屏幕，增减点的数目，并移动点的位置，不再是一个九宫格形状，但保持上述画线的规则不变。

请计算新的解锁屏幕上，一共有多少满足规则的画线方案。

Input

输入文件第一行，为一个整数n，表示点的数目。

接下来n行，每行两个空格分开的整数xi和yi，表示每个点的坐标。

-1000≤xi,Yi≤l000，1≤n<20。各点坐标不相同

Output

输出文件共一行，为题目所求方案数除以100000007的余数。

Sample Input

4

0 0

1 1

2 2

3 3

Sample Output

8

解释：设4个点编号为1到4，方案有1→2→3→4，2→1→3→4，3→2→1→4，2→3→1→4，

及其镜像4→3→2→1,3→4→2→1,2→3→4→1,3→2→4→1.

题解

状压\(dp\)，坑的死

首先好好观察一下模数，它TM不是\(10^9+7\)

。。。

然后考虑状压

设\(f[i][j]\)表示当前状态是\(i\)，当前位置结尾的点是\(j\)的方案数

暴力枚举一下个连接谁，检查它们中间的点是否都已经被选择

如果每次都\(check\)一下，复杂度就会变成\(O(2^nn^3)\)

提前预处理出任意两个点之间的集合，这一步的复杂度是\(O(n^3)\)

计算是否贡献的时候，不要计算出斜率再计算，这样会掉精度

把斜率乘到两边就行了。

然后做\(dp\)的时候就可以\(O(1)\)检查了

这样复杂度就是\(O(n^3+2^nn^2)\)，并且不满。

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define ll long long

#define RG register

#define MOD 100000007

inline int read()

{

RG int x=0,t=1;RG char ch=getchar();

while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

if(ch=='-')t=-1,ch=getchar();

while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

return x*t;

}

int n,X[20],Y[20];

int g[20][20];

int f[20][1<<20];

void update(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

int main()

{

n=read();

for(int i=0;i

for(RG int i=0;i

for(RG int j=0;j

{

if(i==j)continue;

for(RG int k=0;k

{

if(k==i||k==j)continue;

if(X[k]

if(X[k]>X[i]&&X[k]>X[j])continue;

if(Y[k]

if(Y[k]>Y[i]&&Y[k]>Y[j])continue;

if(Y[i]==Y[k])

{

if(Y[j]==Y[k])g[i][j]|=(1<

continue;

}

if(Y[j]==Y[k])continue;

if((X[i]-X[k])*(Y[j]-Y[k])==(X[j]-X[k])*(Y[i]-Y[k]))g[i][j]|=(1<

}

}

for(RG int i=0;i

for(RG int t=0;t<(1<

for(RG int i=0;i

{

if(!(t&(1<

if(!f[i][t])continue;

for(RG int j=0;j

{

if(t&(1<

if((g[i][j]&t)!=g[i][j])continue;

update(f[j][t|(1<

}

}

int ans=0;

for(RG int t=0;t<(1<

{

int tot=0;

for(RG int i=t;i;i-=i&(-i))++tot;

if(tot<4)continue;

for(RG int i=0;i

if(t&(1<

}

printf("%d\n",ans);

return 0;

}