原题链接：https://cses.fi/problemset/task/2181

Counting Tilings

Your task is to count the number of ways you can fill an n×mn×m grid using 1×21×2 and 2×12×1 tiles.

Input

The only input line has two integers nn and mm.

Output

Print one integer: the number of ways modulo 109+710^9 +7.

Constraints

1≤n≤101\le n\le10

1≤m≤10001\le m\le1000

Example

Input:

1
4 7

Output:

1
781

题目描述

有1∗21*2大小的砖，可以横着铺也可以竖着铺，问有多少种不同方法，可以铺满n∗mn*m大小的网格（不考虑对称、翻转等情况）

解决方案

我们把短的边设为水平方向，长的边设为竖直方向，我们从左到右，从上倒下考虑每个格子的情况，假设当前已经处理完第ii行第jj列的格子，情况如下图所示

图中上半部分黑色的格子表示必定已经铺了砖，下半部分白色的部分表示还没铺砖，中间蓝色的那条表示我们在确保黑色的所有格子都有砖之后，可能有砖也可能没有砖的那部分格子，因为每块砖可以竖着铺或者横着铺，且只有1∗21*2大小的砖，所以当前的格子能不能铺砖只受上面的格子和左边的格子影响，因此只需要记录蓝色的那一条格子的状态即可，我们用1表示蓝色的格子已经铺了砖，0表示蓝色的格子还没铺上砖，由于n≤10n\le 10，因此状态的数量最多为210=10242^{10}=1024个，可以用整型变量的二进制形式来表示蓝色的那条格子的状态，该变量记为usedused，用dp[cur][used]dp[cur][used]表示当前处理完(i,j)(i,j)格子后，蓝色格子状态为usedused时的方法数。

由于我们已经处理完了(i,j)(i,j)的那个格子，现在我们来处理下一个格子：(i,j+1)(i,j+1)的格子，下一个格子对应的方法数在计算时记为dp[nxt][used]dp[nxt][used]，(i,j+1)(i,j+1)的格子处理完后对应的状态应该要如下图所示

在处理(i,j+1)(i,j+1)格子的时候一共有3种情况

1.如果第(i−1,j+1)(i-1,j+1)的蓝色格子的状态为0，即没铺砖，则处理(i,j+1)(i,j+1)时必须竖着铺，因为我们必须满足上图的状态（除了最下面的一条蓝色格子，上面的黑色格子都必须铺上砖），如下图所示：

如果第(i−1,j+1)(i-1,j+1)的蓝色格子的状态为1，即已经铺过砖了，处理(i,j+1)(i,j+1)时有另外两种可能性

2.如果jj不是第一列，且第(i,j)(i,j)没铺过砖，则可以横着铺，如下图所示：

3.不管第(i,j)(i,j)有没有铺过砖，第(i,j+1)(i,j+1)都可以选择不铺砖

初始状态

可以等价为：在处理(0,0)(0,0)的格子时，之前的结果中对应蓝条格子全为1时方法数为1，其余情况全为0，如下图所示

即dp[cur][(1<<n)−1]=1dp[cur][(1<<n)-1] = 1，其余均为0

最终状态

处理完(m−1,n−1)(m-1,n-1)的格子后，对应蓝条格子全为1时的方法数为最终结果，即dp[cur][(1<<n)−1]dp[cur][(1<<n)-1]的值

时间复杂度

O(m∗n∗2n)O(m*n*2^n)

代码

我们可以选择遍历前一个格子的used状态（push dp），也可以遍历当前格子的used状态（pull dp），这两种dp实现方式均可

push dp

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
// push dp
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

class Solution {
public:
    void Solve() {
        int n,m;
        while(cin>>n>>m) {
            if (n > m) swap(n,m);
            vector<Mint> dp[2];
            int state_num = 1<<n;
            dp[0].resize(state_num); dp[1].resize(state_num);
            int cur = 0, nxt = 1;
            dp[cur].back() = 1;
            rep(i,0,m) {
                rep(j,0,n) {
                    fill(all(dp[nxt]), 0);
                    rep(used,0,(state_num)) {
                        if ((1<<j) & used) {
                            dp[nxt][used & (~(1<<j))] += dp[cur][used];
                            if (j && !((1<<(j-1)) & used)) {
                                dp[nxt][used | (1<<(j-1))] += dp[cur][used];
                            }
                        } else {
                            dp[nxt][used | (1<<j)] += dp[cur][used];
                        }
                    }
                    swap(cur, nxt);
                }
            }
            cout << dp[cur].back() << endl;
        }
    }
 
private:
};

void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}
 
int main() {
    set_io("input");
    Solution().Solve();
 
    return 0;
}

pull dp

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
// pull dp
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

class Solution {
public:
    void Solve() {
        int n,m;
        while(cin>>n>>m) {
            if (n > m) swap(n,m);
            vector<Mint> dp[2];
            int state_num = 1<<n;
            dp[0].resize(state_num); dp[1].resize(state_num);
            int cur = 0, nxt = 1;
            dp[cur].back() = 1;
            rep(i,0,m) {
                rep(j,0,n) {
                    rep(used,0,(state_num)) {
                        if ((1<<j) & used) {
                            dp[nxt][used] = 0;
                            dp[nxt][used] += dp[cur][used & (~(1<<j))];
                            if (j && ((1<<(j-1)) & used)) {
                                dp[nxt][used] += dp[cur][used & (~(1<<(j-1)))];
                            }
                        } else {
                            dp[nxt][used] = dp[cur][used | (1<<j)];
                        }
                    }
                    swap(cur, nxt);
                }
            }
            cout << dp[cur].back() << endl;
        }
    }
 
private:
};

void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}
 
int main() {
    set_io("input");
    Solution().Solve();
 
    return 0;
}