Massive Algorithms: hihoCoder 1151 : 骨牌覆盖问题・二矩阵快速幂 - 小人物_cipher - 博客频道

hihoCoder 1151 : 骨牌覆盖问题・二矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET

上一周我们研究了2xN的骨牌问题，这一周我们不妨加大一下难度，研究一下3xN的骨牌问题？
所以我们的题目是：对于3xN的棋盘，使用1x2的骨牌去覆盖一共有多少种不同的覆盖方法呢？
首先我们可以肯定，奇数长度一定是没有办法覆盖的；对于偶数长度，比如2，4，我们有下面几种覆盖方式：

提示：3xN骨牌覆盖

输入

第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行：1个整数，表示覆盖方案数 MOD 12357

样例输入

62247088

样例输出

第二题跟第一题相比，就是棋盘的高度从2变成了3，这时我们还想用第一题的方法来解决，那么此时是否还存在像问题一中那样的转移矩阵呢？答案是肯定的，但是此时我们需要真正弄清楚这个转移矩阵的含义了。

首先我们是列为单位进行的转移推算，那么我们要定义一个其状态的表示方法。这里对于每一列，有三个位置，我们分别用0和1表示其对应位置是否填满，则可以用0到7来表示每一列的全部状态了：

然后我们用动态规划的思想进行问题的分解：假设第i列之前（不包括第i列）的所有列都已经被填满，且第i行的状态为x（x是0到7中的一个数），第i+1行的状态为0（全空），此时我们要对第i+1行进行覆盖，并需要保证在覆盖完成之后：第i列的状态为7（被填满），第i+2行的状态为0（全空），这样才可以继续向后递推。
定义了以上的规则之后，我们来看一下第i+1行的覆盖方法（设i+1列的状态为y）：

1. 若x中对应位置状态为0，则必须横向覆盖骨牌，此时完成后对应位置x为1，y也为1。
2. 若x中对应位置状态为1，则i+1行可以：
1) 不覆盖，此时完成后y对应位置为0
2) 竖着覆盖（如果可能）,此时完成后y对应位置为1。

根据以上的递推方式进行枚举，则可以得到x到y的状态转移矩阵M，如下：（空位置为0）

可以举个例子来理解上面的矩阵，比如说第i列的状态为3，则在覆盖第i+1列时，第1行肯定是横着覆盖，第2,3行则既可以不覆盖也可以竖着覆盖，所以转移后y的状态即可能是4也可能是7，即转移矩阵对应位置为1。

有了状态转移矩阵，再来看边界条件：在准备覆盖第1列时，默认第0列的状态肯定是7的，所以初始状态矩阵为

A = [0, 0, 0, 0, 0, 0, 0, 1]

而最终要求的是将第n列全部覆盖的方法数，若B = Mn x A，B是一个1x8的矩阵，则最终的结果为B的第1行第8列的值。具体实现见代码：

#include <iostream>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
#define MOD 12357
typedef long long ll;
 
struct Matrix {
    int m, n;
    vector<vector<ll> > a;
    Matrix(int m, int n) : m(m), n(n) {
        a = vector<vector<ll> >(m, vector<ll>(n));
    }
    Matrix(int m, int n, ll *b) : m(m), n(n) {
        a = vector<vector<ll> >(m, vector<ll>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = b[i*n+j];
            }
        }
    }
 
    void operator*=(const Matrix &r) {
        Matrix res(m, r.n);
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < r.n; col++) {
                for (int k = 0; k < n; k++) {
                    res.a[row][col] += a[row][k] * r.a[k][col];
                    res.a[row][col] %= MOD;
                }
            }
        }
        *this = res;
    }
};
 
int main() {
    ll b[] = { // 转移矩阵
        0, 0, 0, 0, 0, 0, 0, 1,
        0, 0, 0, 0, 0, 0, 1, 0,
        0, 0, 0, 0, 0, 1, 0, 0,
        0, 0, 0, 0, 1, 0, 0, 1,
        0, 0, 0, 1, 0, 0, 0, 0,
        0, 0, 1, 0, 0, 0, 0, 0,
        0, 1, 0, 0, 0, 0, 0, 1,
        1, 0, 0, 1, 0, 0, 1, 0,
    };
    Matrix m(8, 8, b);
    ll a[] = { // 初始状态
        0, 0, 0, 0, 0, 0, 0, 1,
    };
    Matrix A(1, 8, a);
 
    // freopen("..\\input.txt", "r", stdin);
    int N; cin >> N;
    for (int t = 0; t < 32; t++) {
        if (N & (1 << t)) A *= m;
        m *= m;
    }
    cout << A.a.back().back() << endl;
}

前两周里，我们讲解了2xN,3xN骨牌覆盖的问题，并且引入了两种不同的递推方法。
这一次我们再加强一次题目，对于给定的K和N，我们需要去求KxN棋盘的覆盖方案数。
输入

第1行：2个整数N。表示棋盘宽度为k，长度为N。2≤K≤7，1≤N≤100,000,000

输出

第1行：1个整数，表示覆盖方案数 MOD 12357

解题思路

第三题在第二题的基础上再次做了扩展，此时行数K是可变的，而像问题二中那样手动枚举出状态转移矩阵显然是不科学的了，这时就需要我们写代码来求出状态转移矩阵了。

求状态转移矩阵的方法同样是枚举，只不过需要我们写dfs代码来枚举了。与问题二中相同，假设第i-1列的状态为x，第i列的状态为y，则我们要求的状态转移矩阵中对应值应该是从状态x到状态y是否可以成功转移（可以转移为1，不可转移为0）。
值得注意的是，此时的x是转移前第i-1列的状态，y是转移后第i列的状态。而转移前第i列状态应该为0，转移后第i-1列状态应该为7。由此我们可以得到转移方法：

1. 不覆盖：此时需要x对应位置为1，y对应位置为0，列+1
2. 横向覆盖：此时需要x对应位置为0，y对应位置为1，列+1
2. 竖向覆盖：此时需要x和y对应位置以及其下一列的对应位置都为1，列+2

我们可以以状态x=0, y=0开始，从第1列开始枚举，每一列都同时枚举以上三种覆盖方式，当枚举到最后一列时，则表示可以从此时的x转移到y。详见代码。

C++代码

#include <iostream>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
#define MOD 12357
typedef long long ll;
 
struct Matrix {
    int m, n;
    vector<vector<ll> > a;
 
    Matrix(int m, int n) : m(m), n(n) {
        a = vector<vector<ll> >(m, vector<ll>(n));
    }
 
    void operator*=(const Matrix &r) {
        Matrix res(m, r.n);
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < r.n; col++) {
                for (int k = 0; k < n; k++) {
                    res.a[row][col] += a[row][k] * r.a[k][col];
                    res.a[row][col] %= MOD;
                }
            }
        }
        *this = res;
    }
};
 
int K;
// 进入此函数时第i-1列状态为x，第i列状态为y
void dfs(int x, int y, int col, vector<vector<ll> > &d) {
    if (col == K) {
        d[x][y] = 1;
        return;
    }
    // 我的代码
    dfs(x | (1 << col), y, col + 1, d); // 不放置
    dfs(x, y | (1 << col), col + 1, d); // 横向放置
    if (col + 2 <= K) {                 // 竖向放置
        dfs(x | (3 << col), y | (3 << col), col + 2, d);
    }
    /* HihoCoder提示中给的代码
    dfs((x << 1) + 1, y << 1, col + 1, d); // 不放置
    dfs(x << 1, (y << 1) + 1, col + 1, d); // 横向放置
    if (col + 2 <= K) {                    // 竖向放置
        dfs((x << 2) + 3, (y << 2) + 3, col + 2, d);
    }
    */
}
 
void getTransMatrix(vector<vector<ll> > &d) {
    dfs(0, 0, 0, d);
}
 
int main() {
    // freopen("..\\input.txt", "r", stdin);
    cin >> K;
    Matrix m(1<<K, 1<<K); // 转移矩阵
    getTransMatrix(m.a);  // 计算转移矩阵
    Matrix A(1, 1<<K);    // 初始状态
    *(A.a.back().rbegin()) = 1;
 
    int N; cin >> N;
    for (int t = 0; t < 32; t++) {
        if (N & (1 << t)) A *= m;
        m *= m;
    }
    cout << A.a.back().back() << endl;
}

http://sighingnow.github.io/algorithm/domino_tiling_dp.html

Read full article from hihoCoder 1151 : 骨牌覆盖问题・二矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET

hihoCoder 1151 : 骨牌覆盖问题・二矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET

输入

输出

输出

解题思路

C++代码

Labels

Popular Posts

hihoCoder 1151 : 骨牌覆盖问题・二 矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET

输入

输出

输出

解题思路

C++代码

Labels

Popular Posts

hihoCoder 1151 : 骨牌覆盖问题・二矩阵快速幂 - 小人物_cipher - 博客频道 - CSDN.NET