[CQOI2018]解锁屏幕

状压DP

题面

戳我

• $n\leq20$

解析

这数据范围显然是状压。
可以发现，区分不同方案的标准是选的点和终结点。
于是设$dp[now][s]$表示当选点状态为$now$，最后选的点为$s$时的方案数。
然后预处理一下连两点时中间经过的其它点$way[i][j]$（这里注意判断条件问题，不能少等于号）。
再通过$queue$储存、延伸状态，统计时枚举下一个点，枚举中间点判是否路过未经过的点即可。
目测复杂度$O(2^nn^3)$
但是我发现我傻逼了，好像$(way[i][j]\&now)!=way[i][j])$就可以$O(1)$判不合法呢。
于是复杂度降到$O(2^nn^2)$。
然后因用$queue$被卡爆，被迫改成暴枚状态。。。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define mp make_pair
#define ll long long
#define re register
#define il inline
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define fp(i,a,b) for(re int i=a;i<=b-1;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1<<20,mod=1e8+7;
int n,way[30][30],x[30],y[30],dp[30][N],now,s;
ll ans;
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();
  fp(i,0,n) x[i]=gi(),y[i]=gi();
  fp(i,0,n)
    fp(j,0,n)
    fp(k,0,n)
    if(k!=i&&k!=j&&x[k]>=min(x[i],x[j])&&x[k]<=max(x[i],x[j])&&y[k]>=min(y[i],y[j])&&y[k]<=max(y[i],y[j]))
      if((y[k]-y[i])*(x[j]-x[i])==(y[j]-y[i])*(x[k]-x[i])) way[i][j]|=(1<<k);
  fp(i,0,n) dp[i][1<<i]=1;
  fp(now,0,(1<<n))
    fp(s,0,n)
    {
      if(!(now&(1<<s))||!dp[s][now]) continue;
      fp(i,0,n)
    {
      if((1<<i)&now) continue;
      if((way[s][i]&now)!=way[s][i]) continue;
      dp[i][now|(1<<i)]+=dp[s][now];
      if(dp[i][now|(1<<i)]>=mod) dp[i][now|(1<<i)]-=mod;
    }
    }
  fp(now,0,(1<<n))
    {
        re int tot=0,ysn=now;
        for(;ysn;ysn-=ysn&-ysn) ++tot;
    if(tot>3)
      fp(i,0,n) if((1<<i)&now)
        {
          ans+=dp[i][now];
          if(ans>=mod) ans-=mod;
        }
    }
  printf("%lld\n",ans);
  return 0;
}