schtonn

schtonn

0%

各种奇奇怪怪的多米诺骨牌

Posted on Edited on Valine:

前置知识

动态规划，二进制基础知识。

引入

假设我们有一个矩形的棋盘，里面有 \(n\) 行 \(m\) 列的 \(1\times1\) 的方格，现在我们要往里面放 \(1\times2\) 的多米诺骨牌。要求骨牌不能重叠，正好填满棋盘的所有方格。求所有方案数。

这时我们可以利用状态压缩，对每一层进行动态规划。

状态

对于棋盘上的每一个位置，如果该位置上的骨牌覆盖了其下的方格，那么该位置上的状态为1，否则为0。

对于已经覆盖完毕的一整行，将该行每一个位置的状态整合成一个二进制数，这就是这一行的状态。

例如：

一种覆盖情况
一种覆盖情况

在当前情况下，第一行的状态是 \((001)_2\)，第二行的状态是 \((110)_2\)。

对于状态压缩的进一步讲述，在另一篇文章中，这里不多赘述。

状态转移

对于每一个层，状态转移就是看这一层的某一种状态能不能转移到下一层的某一种状态。例如上图的第一行和第二行，就是状态 \((001)_2\)，转移到了状态 \((110)_2\)。这就是一次成功的状态转移。

更进一步的描述，我们需要枚举这一行的每一种状态，以及上一行的每一种状态，检查上一行的状态能否转移到这一行，并且要求上一行的状态是可达的。

检查

这时我们就需要一个函数来检查上一行的状态能否转移到这一行。

  • 我们假设上一行的状态为A，本行的状态为B。

  • 首先检查A，B是否有重叠，如果有那么立即退出。

  • 如果该位置的骨牌覆盖了下一行，那么它一定是竖向放置的。所以设所有竖向放置的骨牌C为A按位或B。

  • 将C取反，结果D即为横向放置的骨牌。D的二进制位中应该是两位一组的。

    因为 \(3=(11)_2\)，所以E=D/3标示了每个两位一组的二进制位中右边一位。如： \[\frac{(1101111)_2}{3}=(0100101)_2\]

  • E按位或E<<1应等于D，因为所有标示都左移了一位，并与原来的按位或。

这就是检查函数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "bits/stdc++.h"
using namespace std;
const int N=1<<10;
const int mod=10007;
int m,n;
int F[110][N+10];//F[i][j]表示骨牌覆盖完前i行，多余的骨牌状态为j的方案总数。
bool T(int A,int B){
    if(A&B)return false;
    int C=A|B;
    int D=C^((1<<n)-1);
    int E=D/3;
    int F=E|(E<<1);
    if(F==D)return true;
    return false;
}
int main(){
    cin>>n>>m;
    F[0][0]=1;
    for(int i=1;i<=m;i++){//行数
        for(int cur=0;cur<=(1<<n)-1;cur++){//枚举本行状态
            for(int pre=0;pre<=(1<<n)-1;pre++){//枚举上一行状态
                int k=T(pre,cur);
                F[i][cur]=(F[i][cur]+F[i-1][pre]*k)%mod;
            }
        }
    }
    cout<<F[m][0]<<endl;
    return 0;
}

拓展

破洞

对于棋盘上有破洞的情况，可以在状态转移的时候使用按位或，这样破洞上就不会放骨牌了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include "bits/stdc++.h"
using namespace std;
const int N=1<<10;
const int mod=10007;
int m,n,p;
int F[100][N];//F[i][j]表示骨牌覆盖完前i行，多余的骨牌状态为j的方案总数。
int hole[100];
bool T(int A,int B){
    int C=A|B;
    int D=C^((1<<n)-1);
    int E=D/3;
    int F=E|(E<<1);
    if(A&B)return false;
    if(F==D)return true;
    return false;
}
int main(){
    cin>>n>>m>>p;
    int x,y;
    for(int i=1;i<=p;i++){
        cin>>x>>y;
        hole[y]|=1<<(x-1);
    }
    if(m==2){
        F[0][hole[1]]=1;
    }else{
        F[0][0]=1;
    }
    for(int i=1;i<=m;i++){//行数
        for(int B=0;B<=(1<<n)-1;B++){//枚举本行状态
            for(int A=0;A<=(1<<n)-1;A++){//枚举上一行状态
                int k=T(A,B|hole[i]);
                F[i][B]=(F[i][B]+F[i-1][A]*k)%mod;
            }
        }
    }
    cout<<F[m][0]<<endl;
    return 0;
}

大数据

如果n小一些，m大亿些，那么可以使用矩阵快速幂，因为每一层之间的转移本质上都是一样的，所以用可以矩阵来代替转移函数。

如果m再大亿些，那么就需要在初始化时加入一点精髓。

矩阵中有的转移可能是永远也用不到的，因为到达不了它的前置状态。这时我们可以用一个数组来记录能到达的状态，只对能到达的状态进行计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include "bits/stdc++.h"
using namespace std;
const int N=1<<5;
const int mod=10007;
int m,n;
bool T(int A,int B){
    if(A&B)return false;
    int C=A|B;
    int D=C^((1<<n)-1);
    int E=D/3;
    // cout<<fact(A)<<','<<fact(B)<<','<<fact(C)<<','<<fact(D)<<','<<fact(E);
    int F=E|(E<<1);
    if(F==D)return true;
    return false;
}
struct matrix{
    int v[N+2][N+2];
    int x,y;
}t,I,ans;
int pre[N+2];
ostream&operator<<(ostream&ous,matrix a){
    for(int i=0;i<a.x;i++){
        for(int j=0;j<a.y;j++){
            ous<<a.v[i][j]<<' ';
        }
        ous<<endl;
    }
    return ous;
}
matrix operator+(matrix a,matrix b){
    matrix c;
    if(a.x!=b.x||a.y!=b.y)return c;
    int x=a.x,y=a.y;
    c.x=x;
    c.y=y;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            c.v[i][j]=(a.v[i][j]+b.v[i][j])%mod;
        }
    }
    return c;
}
matrix operator*(matrix a,matrix b){
    matrix c;
    if(a.y!=b.x)return c;
    int x=a.x,y=b.y,z=a.y;
    c.x=x;
    c.y=y;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            c.v[i][j]=0;
            for(int k=0;k<z;k++){
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]+mod)%mod;
            }
        }
    }
    return c;
}
void init(){
    t.x=t.y=1<<n;
    I.x=I.y=1<<n;
    pre[0]=1;
    for(int i=0;i<=(1<<n)-1;i++){
        for(int j=0;j<=(1<<n)-1;j++){
            if(i==j) I.v[i][j]=1;
            if(pre[i]||pre[j]){
                t.v[i][j]=T(i,j);
                if(t.v[i][j])pre[i]=pre[j]=1;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    init();
    int cnt=m;
    ans=I;
    while(cnt){
        if(cnt&1)ans=ans*t;
        t=t*t;
        cnt>>=1;
    }
    cout<<ans.v[0][0]%mod<<endl;
    return 0;
}

我踩的坑

由于计算机中使用补码计算，所以对C取反的时候要精细考虑。

我一开始使用了 ~ 按位取反，它把整个二进制串都取反了，会出现奇奇怪怪的问题，这时我就想到了按位异或 ^，可以只取反二进制中的一部分。

也就是这一部分代码：

1
int D=C^((1<<n)-1);