前言
状压 DP 就是一类使用根据几进制来进行状态转移方程。
一般来说，数据范围 2 n 2^n 2n 都在情理之中，可是 n ! n! n! 就直接爆炸。
状压一般来说都可以用搜索，并且搜索都可以拿分，只是拿不全。
所以说，一般看见有一维是 11 11 11~ 19 19 19 的话，那可以考虑状压。
题目选讲
Solution
经典的状压 DP，算是入门题目吧。
我们发现 n n n 和 m m m 都特别小，但是搜索肯定过不了，那么我们思考一下状压。
我们发现：每一行的状态可以用一个二进制来表示，每一块草地种或者不种。
而且当前这块草地仅仅受到前一行草地的影响，也就是无后效性，肯定就是打 DP。
我们设 d p i , j dp_{i,j} dpi,j 表示第 i i i 行状态为 j j j 的情况下，有多少种方案数。
这里， j j j 表示出来是十进制数，实际上它表示了一种二进制下的一种状态。
首先排除这一行本身不合法的情况，即存在相邻或者不能种的草地上种了草。
对于这种判断，像我这种蒟蒻只会先用个数组存下来，然后在暴力判断，带一点常数。
大佬们可以尝试用位运算试试，只是很容易出锅。
接着我们枚举上一行，然后再看两行是否有相邻，如果合法了，那么累加就行了。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=13;
const int mod=1e8;
int n,m,ans;
int a[N][N],Log[N],Tag;
int dp[N][1<<N];
bool check(int i,int j){
if(j&(j<<1)) return 1;
int w=m;
while(j){
if(j&1 && !a[i][w]) return 1;
j>>=1;
w--;
}
return 0;
}
int main(){
scanf("%d %d",&n,&m);
Tag=1<<m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=0;i<=Tag;i++) !check(0,i)?dp[0][i]=1:1;
for(int i=1;i<=n;i++)
for(int j=0;j<=Tag;j++){
if(check(i,j)) continue;
for(int k=0;k<=Tag;k++){
if(j&k || check(i-1,k)) continue;
dp[i][j]+=dp[i-1][k];
dp[i][j]%=mod;
}
}
for(int i=0;i<=Tag;i++) ans+=dp[n][i],ans%=mod;
printf("%d",ans);
return 0;
}
Solution
经典的棋盘状压，挺好玩。
观察数据范围，发现 m m m 很小，考虑状压。
可以看到一个炮兵只被上一排和上上一排影响。
那么我们我们的状态定义就很显然：
设 d p i , j , k dp_{i,j,k} dpi,j,k 表示第 i i i 行状态为 j j j，第 i − 1 i-1 i−1 行状态为 k k k 的情况。
然后直接枚举三行的情况，判断是否相邻。
看到这里相信大家都有了一点疑惑： 2 10 × 2 10 × 2 10 × 100 = 107374182400 2^{10}\times 2^{10}\times 2^{10}\times 100=107374182400 210×210×210×100=107374182400
岂不爆炸，实际上，这是一个状压很精髓的地方。
对于一行来讲，本事就有许多状态不合法，就如本身就相邻。
我算了一下，只有： 144 144 144 种情况
那么带进去就有： 298598400 298598400 298598400 的复杂度。
再加上枚举两个删掉一些，和图中本来有一些不能放，就可以排除大部分。
反正一句话：跑不满。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
const int M=1e1+1;
int n,m,Fi,ans;
int dp[N][1<<10][1<<10],Bit[1<<10];
bool Check[N][1<<M],f[11],k[N][M];
bool check(int i,int j){
memset(f,0,sizeof(f));
int x=1;
while(j){
f[x]=(j&1);
j>>=1;
x++;
}
for(int l=1;l<=m;l++) if(f[l] && !k[i][l]) return 0;
return 1;
}
int Count(int x){
int sum=0;
while(x) sum+=x&1,x>>=1;
return sum;
}
int main(){
scanf("%d %d",&n,&m);
Fi=(1<<m)-1;
for(register int i=1;i<=m;i++) k[0][i]=1;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++){
char opt;
cin>>opt;
if(opt=='P') k[i][j]=1;
}
for(register int i=0;i<=Fi;i++)
for(register int j=0;j<=n;j++) (!check(j,i) || i&(i<<1) || i&(i<<2))?1:Check[j][i]=1;
for(register int j1=0;j1<=Fi;j1++){
Bit[j1]=Count(j1);
if(Check[1][j1]) dp[1][j1][0]=Bit[j1];
}
for(register int i=2;i<=n;i++)
for(register int j1=0;j1<=Fi;j1++)
if(Check[i][j1])
for(register int j2=0;j2<=Fi;j2++)
if(Check[i-1][j2] && !(j1&j2))
for(register int j3=0;j3<=Fi;j3++)
if(Check[i-2][j3])
if(!(j1&j2) && !(j2&j3) && !(j1&j3)) dp[i][j1][j2]=max(dp[i-1][j2][j3]+Bit[j1],dp[i][j1][j2]);
for(register int i=0;i<=Fi;i++)
for(register int j=0;j<=Fi;j++) ans=max(dp[n][i][j],ans);
printf("%d",ans);
return 0;
}
Solution
感觉也很好玩。
我们知道，三点确定一个抛物线，这里已经给出了原点，即两点确定一条抛物线。
我们先把所有的抛物线整出来。
先推一下式子。
{ a ⋅ A x 2 + b ⋅ A x = A y a ⋅ B x 2 + b ⋅ B x = B y \begin{cases}a\cdot A_x^2+b\cdot A_x=A_y\\a\cdot B_x^2+b\cdot B_x=B_y\end{cases} {a⋅Ax2+b⋅Ax=Aya⋅Bx2+b⋅Bx=By
设参数 k = A x 2 B x 2 k=\frac{A_x^2}{B_x^2} k=Bx2Ax2
第二个式子乘上参数：
a ⋅ A x 2 + k ⋅ b ⋅ B x = k ⋅ B y \begin{aligned} a\cdot A_x^2+k\cdot b\cdot B_x&=k\cdot B_y\end{aligned} a⋅Ax2+k⋅b⋅Bx=k⋅By
让一式减去二式：
b ⋅ A x − k ⋅ b ⋅ B x = A y − k ⋅ B y b ⋅ ( A x − k ⋅ B x ) = A y − k ⋅ B y b = A y − k ⋅ B y A x − k ⋅ B x \begin{aligned}b\cdot A_x-k\cdot b\cdot B_x&=A_y-k\cdot B_y \\ b\cdot(A_x-k\cdot B_x) &=A_y-k\cdot B_y \\ b &=\frac{A_y-k\cdot B_y}{A_x-k\cdot B_x} \end{aligned} b⋅Ax−k⋅b⋅Bxb⋅(Ax−k⋅Bx)b=Ay−k⋅By=Ay−k⋅By=Ax−k⋅BxAy−k⋅By
通过这样我们就把 b b b 给解出来了。
随便带进去，带到一式吧。
a ⋅ A x 2 = A y − b ⋅ A x a = A y − b ⋅ A x A x 2 \begin{aligned}a\cdot A_x^2 &= A_y-b\cdot A_x \\ a &= \frac{A_y-b\cdot A_x}{A_x^2} \end{aligned} a⋅Ax2a=Ay−b⋅Ax=Ax2Ay−b⋅Ax
就这么解完了。
由于一条抛物线可能经过多个点，所以我们把每一条抛物线跑一遍，用二进制表示出其能经过哪些点。
然后问题就转化成了一个背包问题。
在这里，就把每个抛物线的价值进行了状压。
Code
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
int T,n,m,cnt;
int Fc[400],dp[1<<19];
struct node{
double x,y;
}a[19];
struct Par{
double a,b;
}f[400];
bool Check(int i,int j){
return fabs(a[j].y-(f[i].a*a[j].x*a[j].x+f[i].b*a[j].x))<0.000001;
}
int main(){
scanf("%d",&T);
while(T--){
cnt=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
double k=(a[i].x*a[i].x)/(a[j].x*a[j].x),A,B;
B=(a[i].y-k*a[j].y)/(a[i].x-k*a[j].x);
A=(a[i].y-a[i].x*B)/(a[i].x*a[i].x);
if(A<0) f[++cnt]=((Par){A,B});
}
mem(Fc,0);
mem(dp,0x3f);
dp[0]=0;
int ans=0;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=n;j++) Fc[i]=Fc[i]*2+Check(i,j);
}
for(int i=1;i<=n;i++) Fc[++cnt]=1<<i-1;
for(int i=0;i<=(1<<n)-1;i++)
for(int j=1;j<=cnt;j++) dp[i|Fc[j]]=min(dp[i|Fc[j]],dp[i]+1);
printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}
Solution
感觉全部题最难的一道，最好玩的。
{ a 3 ⋅ a 9 ⋅ a . . . 2 ⋅ a 6 ⋅ a 18 ⋅ a . . . 4 ⋅ a 12 ⋅ a 36 ⋅ a . . . . . . . . . . . . . . . } \begin{Bmatrix}a & 3\cdot a & 9\cdot a & ...\\ 2\cdot a & 6\cdot\ a & 18\cdot a & ... \\ 4\cdot a & 12\cdot a & 36\cdot a & ...\\... &... &...&... \end{Bmatrix} ⎩⎪⎪⎨⎪⎪⎧a2⋅a4⋅a...3⋅a6⋅ a12⋅a...9⋅a18⋅a36⋅a...............⎭⎪⎪⎬⎪⎪⎫
通过观察这个矩阵我们发现，不能取这个矩阵相邻的元素作为集合。
那么这不禁让我们想起了第一题，而且对于矩阵的大小，是 log \log log 级别的。
那么我们的方法就显而易见了。
对于这个矩阵，我们把所有没有出现过的元素标记上，这样就避免了重复的计算。
当我们算完了一个矩阵，需要进行相乘，因为肯定任意两个矩阵互相还是可以取，就是乘法原理。
万一矩阵的数量太多，跑飞了怎么办？
别慌，我们来想一想。
我跑了一下 1 0 5 10^5 105，跑了 33333 33333 33333 个矩阵。
那接下来我们算一下一个矩阵的复杂度。
约是 10000 10000 10000 级别的样子，但是跑不满，因此还是可以过的，况且随着矩阵越来越多，状态就越来越少，因为越来越多的数都会被标记。
Code
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N=5e6+5;
const int mod=1e9+1;
int Fi,a[19][12],dp[18][5096];
int n,ans=1,Len[18],dq[18];
bool f[N],flag[18][12];
void Work(int x){
mem(a,0);
a[1][1]=x;
int m=1,sum=0,len=0;
for(int i=2;a[1][i-1]*3<=n;i++){
a[1][i]=a[1][i-1]*3;
m++;
}
for(int j=1;j<=m;j++)
for(int i=2;a[i-1][j]*2<=n;i++) a[i][j]=a[i-1][j]*2;
mem(Len,0);
for(int i=1;a[i][1];i++){
for(int j=1;j<=m;j++){
Len[i]=Len[i]*2+(!a[i][j]);
if(!a[i][j]) flag[i][j]=1;
f[a[i][j]]=1;
}
len++;
}
mem(dp,0);
dp[0][0]=1;
for(int i=1;i<=len;i++){
for(int j1=0;j1<=(1<<m)-1;j1++){
if(Len[i]&j1 || j1&(j1<<1)) continue;
for(int j2=0;j2<=(1<<m)-1;j2++){
if(Len[i-1]&j2 || j2&(j2<<1) || j1&j2) continue;
dp[i][j1]+=dp[i-1][j2];
dp[i][j1]%=mod;
}
}
}
for(int i=0;i<=(1<<m)-1;i++) sum+=dp[len][i],sum%=mod;
ans=(1ll*ans*sum)%mod;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
if(!f[i]){
f[i]=1;
Work(i);
}
}
printf("%d",ans);
return 0;
}
Solution
这题在洛谷上使用是标算二十倍的算法卡得过去。
做得最爽的一道题。
首先还是思考如何将这个问题转化为状压。
其实这个题的连线和状压的另一种版题有点像，就是说传球，但是中间的直线需要另行判断。
什么直线呢？
就是说因为两点的直线必须是中间经过的点是使用过的。
可以很自然的想到直接枚举一层 n n n，然后暴力判断斜率。
O ( 2 n ⋅ n 3 ) O(2^n\cdot n^3) O(2n⋅n3)
8388608000 8388608000 8388608000，这么大，但是考虑到状压本身跑不满，因此复杂度虽然比这个小，但还是跑不过。
考虑位运算优化，我们先把任意两点间连线有的点给预处理下来。
然后进行状压取反后再和实际状态做与运算。
Code
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int mod=1e8+7;
int n,Fi;
int dp[20][1<<19];
int sum[1<<19],check[20][20];
bool f[20];
struct node{
int x,y;
}a[20];
inline int qr(){
int s=0,f=1;
char ch;
ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*f;
}
inline void qw(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) qw(x/10);
putchar(x%10+'0');
}
inline bool cmp(node x,node y){
if(x.x==y.x) return x.y<y.y;
return x.x<y.x;
}
inline void opt(int x){
mem(f,0);
int w=1;
while(x) f[w]=(x&1),x>>=1,w++;
}
inline int Count(int x){
int sum=0;
while(x) sum+=x&1,x>>=1;
return sum;
}
inline int Checker(int x,int y){
mem(f,0);
if(x>y) swap(x,y);
int FF=0;
if(x+1==y || x==y) return 0;
for(int i=x+1;i<y;i++) if((a[x].x-a[i].x)*(a[i].y-a[y].y)==(a[i].x-a[y].x)*(a[x].y-a[i].y)) f[i]=1;
for(int i=1;i<=n;i++) FF+=f[i]?1<<i-1:0;
return FF;
}
int main(){
n=qr();
Fi=(1<<n)-1;
for(register int i=1;i<=n;i++) a[i]=((node){qr(),qr()});
sort(a+1,a+1+n,cmp);
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++) check[i][j]=Checker(i,j);
for(register int i=1;i<=n;i++) dp[i][1<<i-1]=1;
for(register int j=0;j<=Fi;j++){
opt(j);
for(register int i=1;i<=n;i++){
if(!f[i]) continue;
for(register int k=1;k<=n;k++)
if(f[k] && !(check[i][k]&(~j)) && k!=i) dp[i][j]+=dp[k][j-(1<<i-1)],dp[i][j]%=mod;
sum[j]+=dp[i][j];
sum[j]%=mod;
}
}
int ans=0;
for(register int j=0;j<=Fi;j++){
if(Count(j)>=4) ans+=sum[j],ans%=mod;
}
printf("%d",ans);
return 0;
}
```# 前言
状压 DP 就是一类使用根据几进制来进行状态转移方程。
一般来说，数据范围 $2^n$ 都在情理之中，可是 $n!$ 就直接爆炸。
状压一般来说都可以用搜索，并且搜索都可以拿分，只是拿不全。
所以说，一般看见有一维是 $11$~$19$ 的话，那可以考虑状压。
# 题目选讲
* [P1879 ](https://www.luogu.com.cn/problem/P1879)
**Solution**
经典的状压 DP，算是入门题目吧。
我们发现 $n$ 和 $m$ 都特别小，但是搜索肯定过不了，那么我们思考一下状压。
我们发现：每一行的状态可以用一个二进制来表示，每一块草地种或者不种。
而且当前这块草地仅仅受到前一行草地的影响，也就是无后效性，肯定就是打 DP。
我们设 $dp_{i,j}$ 表示第 $i$ 行状态为 $j$ 的情况下，有多少种方案数。
这里，$j$ 表示出来是十进制数，实际上它表示了一种二进制下的一种状态。
首先排除这一行本身不合法的情况，即存在相邻或者不能种的草地上种了草。
对于这种判断，像我这种蒟蒻只会先用个数组存下来，然后在暴力判断，带一点常数。
大佬们可以尝试用位运算试试，~~只是很容易出锅。~~
接着我们枚举上一行，然后再看两行是否有相邻，如果合法了，那么累加就行了。
**Code**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=13;
const int mod=1e8;
int n,m,ans;
int a[N][N],Log[N],Tag;
int dp[N][1<<N];
bool check(int i,int j){
if(j&(j<<1)) return 1;
int w=m;
while(j){
if(j&1 && !a[i][w]) return 1;
j>>=1;
w--;
}
return 0;
}
int main(){
scanf("%d %d",&n,&m);
Tag=1<<m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=0;i<=Tag;i++) !check(0,i)?dp[0][i]=1:1;
for(int i=1;i<=n;i++)
for(int j=0;j<=Tag;j++){
if(check(i,j)) continue;
for(int k=0;k<=Tag;k++){
if(j&k || check(i-1,k)) continue;
dp[i][j]+=dp[i-1][k];
dp[i][j]%=mod;
}
}
for(int i=0;i<=Tag;i++) ans+=dp[n][i],ans%=mod;
printf("%d",ans);
return 0;
}
Solution
经典的棋盘状压，挺好玩。
观察数据范围，发现 m m m 很小，考虑状压。
可以看到一个炮兵只被上一排和上上一排影响。
那么我们我们的状态定义就很显然：
设 d p i , j , k dp_{i,j,k} dpi,j,k 表示第 i i i 行状态为 j j j，第 i − 1 i-1 i−1 行状态为 k k k 的情况。
然后直接枚举三行的情况，判断是否相邻。
看到这里相信大家都有了一点疑惑： 2 10 × 2 10 × 2 10 × 100 = 107374182400 2^{10}\times 2^{10}\times 2^{10}\times 100=107374182400 210×210×210×100=107374182400
岂不爆炸，实际上，这是一个状压很精髓的地方。
对于一行来讲，本事就有许多状态不合法，就如本身就相邻。
我算了一下，只有： 144 144 144 种情况
那么带进去就有： 298598400 298598400 298598400 的复杂度。
再加上枚举两个删掉一些，和图中本来有一些不能放，就可以排除大部分。
反正一句话：跑不满。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
const int M=1e1+1;
int n,m,Fi,ans;
int dp[N][1<<10][1<<10],Bit[1<<10];
bool Check[N][1<<M],f[11],k[N][M];
bool check(int i,int j){
memset(f,0,sizeof(f));
int x=1;
while(j){
f[x]=(j&1);
j>>=1;
x++;
}
for(int l=1;l<=m;l++) if(f[l] && !k[i][l]) return 0;
return 1;
}
int Count(int x){
int sum=0;
while(x) sum+=x&1,x>>=1;
return sum;
}
int main(){
scanf("%d %d",&n,&m);
Fi=(1<<m)-1;
for(register int i=1;i<=m;i++) k[0][i]=1;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++){
char opt;
cin>>opt;
if(opt=='P') k[i][j]=1;
}
for(register int i=0;i<=Fi;i++)
for(register int j=0;j<=n;j++) (!check(j,i) || i&(i<<1) || i&(i<<2))?1:Check[j][i]=1;
for(register int j1=0;j1<=Fi;j1++){
Bit[j1]=Count(j1);
if(Check[1][j1]) dp[1][j1][0]=Bit[j1];
}
for(register int i=2;i<=n;i++)
for(register int j1=0;j1<=Fi;j1++)
if(Check[i][j1])
for(register int j2=0;j2<=Fi;j2++)
if(Check[i-1][j2] && !(j1&j2))
for(register int j3=0;j3<=Fi;j3++)
if(Check[i-2][j3])
if(!(j1&j2) && !(j2&j3) && !(j1&j3)) dp[i][j1][j2]=max(dp[i-1][j2][j3]+Bit[j1],dp[i][j1][j2]);
for(register int i=0;i<=Fi;i++)
for(register int j=0;j<=Fi;j++) ans=max(dp[n][i][j],ans);
printf("%d",ans);
return 0;
}
Solution
感觉也很好玩。
我们知道，三点确定一个抛物线，这里已经给出了原点，即两点确定一条抛物线。
我们先把所有的抛物线整出来。
先推一下式子。
{ a ⋅ A x 2 + b ⋅ A x = A y a ⋅ B x 2 + b ⋅ B x = B y \begin{cases}a\cdot A_x^2+b\cdot A_x=A_y\\a\cdot B_x^2+b\cdot B_x=B_y\end{cases} {a⋅Ax2+b⋅Ax=Aya⋅Bx2+b⋅Bx=By
设参数 k = A x 2 B x 2 k=\frac{A_x^2}{B_x^2} k=Bx2Ax2
第二个式子乘上参数：
a ⋅ A x 2 + k ⋅ b ⋅ B x = k ⋅ B y \begin{aligned} a\cdot A_x^2+k\cdot b\cdot B_x&=k\cdot B_y\end{aligned} a⋅Ax2+k⋅b⋅Bx=k⋅By
让一式减去二式：
b ⋅ A x − k ⋅ b ⋅ B x = A y − k ⋅ B y b ⋅ ( A x − k ⋅ B x ) = A y − k ⋅ B y b = A y − k ⋅ B y A x − k ⋅ B x \begin{aligned}b\cdot A_x-k\cdot b\cdot B_x&=A_y-k\cdot B_y \\ b\cdot(A_x-k\cdot B_x) &=A_y-k\cdot B_y \\ b &=\frac{A_y-k\cdot B_y}{A_x-k\cdot B_x} \end{aligned} b⋅Ax−k⋅b⋅Bxb⋅(Ax−k⋅Bx)b=Ay−k⋅By=Ay−k⋅By=Ax−k⋅BxAy−k⋅By
通过这样我们就把 b b b 给解出来了。
随便带进去，带到一式吧。
a ⋅ A x 2 = A y − b ⋅ A x a = A y − b ⋅ A x A x 2 \begin{aligned}a\cdot A_x^2 &= A_y-b\cdot A_x \\ a &= \frac{A_y-b\cdot A_x}{A_x^2} \end{aligned} a⋅Ax2a=Ay−b⋅Ax=Ax2Ay−b⋅Ax
就这么解完了。
由于一条抛物线可能经过多个点，所以我们把每一条抛物线跑一遍，用二进制表示出其能经过哪些点。
然后问题就转化成了一个背包问题。
在这里，就把每个抛物线的价值进行了状压。
Code
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
int T,n,m,cnt;
int Fc[400],dp[1<<19];
struct node{
double x,y;
}a[19];
struct Par{
double a,b;
}f[400];
bool Check(int i,int j){
return fabs(a[j].y-(f[i].a*a[j].x*a[j].x+f[i].b*a[j].x))<0.000001;
}
int main(){
scanf("%d",&T);
while(T--){
cnt=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
double k=(a[i].x*a[i].x)/(a[j].x*a[j].x),A,B;
B=(a[i].y-k*a[j].y)/(a[i].x-k*a[j].x);
A=(a[i].y-a[i].x*B)/(a[i].x*a[i].x);
if(A<0) f[++cnt]=((Par){A,B});
}
mem(Fc,0);
mem(dp,0x3f);
dp[0]=0;
int ans=0;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=n;j++) Fc[i]=Fc[i]*2+Check(i,j);
}
for(int i=1;i<=n;i++) Fc[++cnt]=1<<i-1;
for(int i=0;i<=(1<<n)-1;i++)
for(int j=1;j<=cnt;j++) dp[i|Fc[j]]=min(dp[i|Fc[j]],dp[i]+1);
printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}
Solution
感觉全部题最难的一道，最好玩的。
{ a 3 ⋅ a 9 ⋅ a . . . 2 ⋅ a 6 ⋅ a 18 ⋅ a . . . 4 ⋅ a 12 ⋅ a 36 ⋅ a . . . . . . . . . . . . . . . } \begin{Bmatrix}a & 3\cdot a & 9\cdot a & ...\\ 2\cdot a & 6\cdot\ a & 18\cdot a & ... \\ 4\cdot a & 12\cdot a & 36\cdot a & ...\\... &... &...&... \end{Bmatrix} ⎩⎪⎪⎨⎪⎪⎧a2⋅a4⋅a...3⋅a6⋅ a12⋅a...9⋅a18⋅a36⋅a...............⎭⎪⎪⎬⎪⎪⎫
通过观察这个矩阵我们发现，不能取这个矩阵相邻的元素作为集合。
那么这不禁让我们想起了第一题，而且对于矩阵的大小，是 log \log log 级别的。
那么我们的方法就显而易见了。
对于这个矩阵，我们把所有没有出现过的元素标记上，这样就避免了重复的计算。
当我们算完了一个矩阵，需要进行相乘，因为肯定任意两个矩阵互相还是可以取，就是乘法原理。
万一矩阵的数量太多，跑飞了怎么办？
别慌，我们来想一想。
我跑了一下 1 0 5 10^5 105，跑了 33333 33333 33333 个矩阵。
那接下来我们算一下一个矩阵的复杂度。
约是 10000 10000 10000 级别的样子，但是跑不满，因此还是可以过的，况且随着矩阵越来越多，状态就越来越少，因为越来越多的数都会被标记。
Code
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N=5e6+5;
const int mod=1e9+1;
int Fi,a[19][12],dp[18][5096];
int n,ans=1,Len[18],dq[18];
bool f[N],flag[18][12];
void Work(int x){
mem(a,0);
a[1][1]=x;
int m=1,sum=0,len=0;
for(int i=2;a[1][i-1]*3<=n;i++){
a[1][i]=a[1][i-1]*3;
m++;
}
for(int j=1;j<=m;j++)
for(int i=2;a[i-1][j]*2<=n;i++) a[i][j]=a[i-1][j]*2;
mem(Len,0);
for(int i=1;a[i][1];i++){
for(int j=1;j<=m;j++){
Len[i]=Len[i]*2+(!a[i][j]);
if(!a[i][j]) flag[i][j]=1;
f[a[i][j]]=1;
}
len++;
}
mem(dp,0);
dp[0][0]=1;
for(int i=1;i<=len;i++){
for(int j1=0;j1<=(1<<m)-1;j1++){
if(Len[i]&j1 || j1&(j1<<1)) continue;
for(int j2=0;j2<=(1<<m)-1;j2++){
if(Len[i-1]&j2 || j2&(j2<<1) || j1&j2) continue;
dp[i][j1]+=dp[i-1][j2];
dp[i][j1]%=mod;
}
}
}
for(int i=0;i<=(1<<m)-1;i++) sum+=dp[len][i],sum%=mod;
ans=(1ll*ans*sum)%mod;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
if(!f[i]){
f[i]=1;
Work(i);
}
}
printf("%d",ans);
return 0;
}
Solution
这题在洛谷上使用是标算二十倍的算法卡得过去。
做得最爽的一道题。
首先还是思考如何将这个问题转化为状压。
其实这个题的连线和状压的另一种版题有点像，就是说传球，但是中间的直线需要另行判断。
什么直线呢？
就是说因为两点的直线必须是中间经过的点是使用过的。
可以很自然的想到直接枚举一层 n n n，然后暴力判断斜率。
O ( 2 n ⋅ n 3 ) O(2^n\cdot n^3) O(2n⋅n3)
8388608000 8388608000 8388608000，这么大，但是考虑到状压本身跑不满，因此复杂度虽然比这个小，但还是跑不过。
考虑位运算优化，我们先把任意两点间连线有的点给预处理下来。
然后进行状压取反后再和实际状态做与运算。
Code
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int mod=1e8+7;
int n,Fi;
int dp[20][1<<19];
int sum[1<<19],check[20][20];
bool f[20];
struct node{
int x,y;
}a[20];
inline int qr(){
int s=0,f=1;
char ch;
ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*f;
}
inline void qw(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) qw(x/10);
putchar(x%10+'0');
}
inline bool cmp(node x,node y){
if(x.x==y.x) return x.y<y.y;
return x.x<y.x;
}
inline void opt(int x){
mem(f,0);
int w=1;
while(x) f[w]=(x&1),x>>=1,w++;
}
inline int Count(int x){
int sum=0;
while(x) sum+=x&1,x>>=1;
return sum;
}
inline int Checker(int x,int y){
mem(f,0);
if(x>y) swap(x,y);
int FF=0;
if(x+1==y || x==y) return 0;
for(int i=x+1;i<y;i++) if((a[x].x-a[i].x)*(a[i].y-a[y].y)==(a[i].x-a[y].x)*(a[x].y-a[i].y)) f[i]=1;
for(int i=1;i<=n;i++) FF+=f[i]?1<<i-1:0;
return FF;
}
int main(){
n=qr();
Fi=(1<<n)-1;
for(register int i=1;i<=n;i++) a[i]=((node){qr(),qr()});
sort(a+1,a+1+n,cmp);
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++) check[i][j]=Checker(i,j);
for(register int i=1;i<=n;i++) dp[i][1<<i-1]=1;
for(register int j=0;j<=Fi;j++){
opt(j);
for(register int i=1;i<=n;i++){
if(!f[i]) continue;
for(register int k=1;k<=n;k++)
if(f[k] && !(check[i][k]&(~j)) && k!=i) dp[i][j]+=dp[k][j-(1<<i-1)],dp[i][j]%=mod;
sum[j]+=dp[i][j];
sum[j]%=mod;
}
}
int ans=0;
for(register int j=0;j<=Fi;j++){
if(Count(j)>=4) ans+=sum[j],ans%=mod;
}
printf("%d",ans);
return 0;
}