[状压DP] Previous Practice CQOI2018 解锁屏幕 | Android

传送门

考虑状压
对于集合 $S$， $f[S][x]$表示目前在 $x$的方案数
有转移：
$f[S][x]=\sum_{y\to x} f[S-x][y]$

复杂度 $O(n^32^n)$，因为每次判断复杂度 $O(n)$
显然过不去

考虑优化
预处理优化

验证集合包含（ $P\subseteq S$）
$P \& S=P$

位运算只日龙
多打括号

印度女工在线罢工

#include<bits/stdc++.h>
using namespace std;
#define in Read()
int in{int i=0,f=1;char ch=0;while(!isdigit(ch)&&ch!='-') ch=getchar();if(ch=='-') ch=getchar(),f=-1;while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar();return i*f;
}const int N=1<<21;
const int mod=1e8+7;
int n,f[N][50],line[50][50],ans;
struct Dots{int x,y;
}p[50];int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}bool collineation(Dots u,Dots v,Dots w){return (u.x-v.x)*(v.y-w.y)==(u.y-v.y)*(v.x-w.x);
}void init(){for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(i!=j)for(int k=1;k<=n;++k)if(k!=i&&k!=j)if(min(p[i].x,p[j].x)<=p[k].x&&p[k].x<=max(p[i].x,p[j].x))if(min(p[i].y,p[j].y)<=p[k].y&&p[k].y<=max(p[i].y,p[j].y))if(collineation(p[i],p[j],p[k]))line[i][j]+=(1<<(k-1));return;
}int get_siz(int S){int res=0;while(S){res+=(S&1);S>>=1;}return res;
}bool check(int S,int i,int j){return (line[i][j]&S)==line[i][j];
}int main(){n=in;for(int i=1;i<=n;++i) p[i].x=in,p[i].y=in;init();for(int S=1;S<(1<<n);++S){int siz=get_siz(S);for(int i=1;i<=n;++i){if(!(S&(1<<(i-1)))) continue;if(!(S>>(i-1))) break;if(siz==1){f[S][i]=1;break;}for(int j=1;j<=n;++j){if(i==j) continue;if(!(S&(1<<(j-1)))) continue;if(check(S,i,j)) f[S][i]=add(f[S][i],f[S^(1<<(i-1))][j]);}if(siz>=4) ans=add(ans,f[S][i]);}}printf("%d\n",ans);// for(int i=1;i<=n;++i){// for(int j=1;j<=n;++j)// cout<<line[i][j]<<" ";// cout<<endl;// }return 0;
}