POJ 3420 Quad Tiling【矩阵快速幂+DP】

题目链接:POJ 3420 Quad Tiling

题目大意:和POJ2663基本一个套路,就是更加复杂了些。往一个4*N的矩形中填入2*1的小矩形的种数,由于答案过大,每个case都指定了M。

解题思路:

我将通过这道题,让矩阵快速幂这种类型的题目完全解决。

我们知道,矩阵快速幂,是可以快速求解递推式某项值的一种高效的解法。基于快速幂运算,可以使得幂运算的复杂度从O(N)变为O(logN)

对于POJ3420这题,如果列数不固定,且较小的话,那么可以考虑采用状压DP求解。但是这道题列数为4,那么很容易枚举出DP的转移方程。

我们考虑在我们尽力铺满第n行的时候,可能会“突出”到n+1行,这种情况是可以枚举出来的。

我们不妨如下定义,当铺满第n行后,“突出”到n+1行的情况只有一下几种:(插图来自于http://blog.sina.com.cn/s/blog_69c3f0410100vnhj.html

接下来进行状态转移:

  • a_n=a_{n-1}+b_{n-1}+c_{n-1}+d_{n-1}
  • b_n=a_{n-1}
  • c_n=a_{n-1}+e_{n-1}
  • dx_n=a_{n-1}+dy_{n-1}
  • dy_n=a_{n-1}+dx_{n-1}
  • e_n=c_{n-1}

令d_n=dx_n+dy_n则,状态转移方程为:

  • a_n=a_{n-1}+b_{n-1}+c_{n-1}+d_{n-1}
  • b_n=a_{n-1}
  • c_n=a_{n-1}+e_{n-1}
  • d_n=2*a_{n-1}+d_{n-1}
  • e_n=c_{n-1}

所以我们可以构造矩阵

[[1, 1, 1, 1, 0],
 [1, 0, 0, 0, 0],
 [1, 0, 0, 0, 1],
 [2, 0, 0, 1, 0],
 [0, 0, 1, 0, 0]]

接下来就是套模板了:

矩阵快速幂+DP解这道题的代码如下:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;

int N, M;

mat mul(mat &A, mat &B) {
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++) {
        for (int k = 0; k < B.size(); k++) {
            for (int j = 0; j < B[0].size(); j++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
            }
        }
    }
    return C;
}

mat pow(mat &A, ll n) {
    mat B(A.size(), vec(A[0].size()));
    for (int i = 0; i < A.size(); i++) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main() {
    while (~scanf("%d%d", &N, &M)) {
        if (!N && !M) break;
        mat A(5, vec(5));
        A[0][0] = A[0][1] = A[0][2] = A[0][3] = 1;
        A[1][0] = 1;
        A[2][0] = A[2][4] = 1;
        A[3][0] = 2; A[3][3] = 1;
        A[4][2] = 1;
        A = pow(A, N);
        printf("%d\n", A[0][0]);
    }
    return 0;
}

本人在校生,如有不足之处敬请指正!

发表评论

电子邮件地址不会被公开。 必填项已用*标注