POJ 3420 Quad Tiling 题解 《挑战程序设计竞赛》

POJ 3420 Quad Tiling

贴瓷砖：4*N的地板上用2*1的瓷砖铺满，求所有方案数对M求余。

3.4熟练掌握动态规划

矩阵的幂

久违地上了节课，太无聊，只好刷一题。

假设S[n]表示填满n时的方案数，有S[0]=1。定义矩阵

Mat[p][q] := 边缘p和边缘q可以拼合时取1，否则取0

所谓的可以拼合表示，两个边缘拼起来后长度为1（为2就拼接不起来了，顶住了呀），且内部缝隙可以用2*1的瓷砖填满。

那么Mat就有一些简单的性质了，比如Mat的第一行应该是：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

表示0000只能与1111拼合。

那么[0,0,0,…,S[n]]^T = Mat * [0,0,0,…,S[n-1]]^T = Matⁿ * [0,0,0,…,1]^T 。

问题归结于如何求Mat，最蠢的方式是可以手工人肉搜索：

箭头两边分别表示边缘p和另一些边缘可以拼合，将二进制转为整型填入矩阵可得：

1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 
0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

如果要使用上述递推式的话，需要将此矩阵转置为：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 
1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1

也可以利用位运算来枚举，对于边缘p，考察边缘q，执行异或运算p^q得到的拼合后的情况，如果某一位是1，表示互补（1+0），否则表示恰好有空隙（0+0，在处理中通过取子集的补集避免了1+1；这是由半加运算的性质决定的）。只要数一数连续缺口的数量是否都是偶数就可以知道两者是否可以拼合了。

#include <cstdio>
#include <vector>

using namespace std;

typedef long long LL;
LL MOD;
#define S 4
int N;

struct Matrix : vector<vector<LL> >
{
    int height, width;

    Matrix()
    {}

    Matrix(int height, int width) : height(height), width(width)
    {
        assign(height, vector<LL>(width, 0));
    }

    Matrix operator*(const Matrix &m)
    {
        Matrix ret(this->height, m.width);

        for (int i = 0; i < this->height; ++i)
        {
            for (int k = 0; k < this->width; ++k)
            {
                for (int j = 0; j < m.width; ++j)
                {
                    ret[i][j] += (*this)[i][k] * m[k][j];
                    ret[i][j] %= MOD;
                    if (ret[i][j] < 0)
                    {
                        ret[i][j] += MOD;
                    }
                }
            }
        }

        return ret;
    }

    vector<LL> operator*(const vector<LL> &v)
    {
        vector<LL> ret((*this).height);

        for (int i = 0; i < (*this).height; ++i)
        {
            for (int j = 0; j < (*this).width; ++j)
            {
                ret[i] += (*this)[i][j] * v[j];
                ret[i] %= MOD;
                if (ret[i] < 0)
                {
                    ret[i] += MOD;
                }
            }
        }

        return ret;
    }

    Matrix pow(const LL k)
    {
        Matrix ret = get_identity((*this).width), base = (*this);

        for (LL e = k; e; e >>= 1)
        {
            if (e & 1)
            {
                ret = ret * base;
            }
            base = base * base;
        }

        return ret;
    }

    static Matrix get_identity(int size)
    {
        Matrix ret(size, size);
        for (int i = 0; i < size; ++i)
        {
            ret[i][i] = 1;
        }
        return ret;
    }
};

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    // 制作矩阵
    Matrix mat(1 << S, 1 << S);
    for (int bit = 0; bit < 1 << S; ++bit)
    {
        for (int sub = bit; ; sub = bit & (sub - 1))      // 枚举子集
        {
            const int cur_status = bit ^sub;              // 两个缺口拼合，0代表缝隙
            bool match = true;                            // 是否匹配
            int continuous_one_count = 0;                  // 连续的单元缝隙的个数
            for (int i = 0; i < S; ++i)
            {
                if ((cur_status >> i) & 1)
                {
                    ++continuous_one_count;
                }
                else
                {
                    match &= (continuous_one_count & 1) == 0; // 连续的单元缝隙为偶数说明匹配（往里面塞2*1的砖块就可填满）
                    continuous_one_count = 0;
                }
            }
            match &= (continuous_one_count & 1) == 0;
            if (match)
            {
                ++mat[bit][((1 << S) - 1) ^ sub];    // 垂直翻转，之后mat[x][y]表示x与y可以拼合
            }
            if (sub == 0)
            {
                break;
            }
        }
    }
    vector<LL> v(1 << S, 0);
    v[(1 << S) - 1] = 1;                    // 长度为0的时候，只有一种方案
    while (scanf("%d%lld", &N, &MOD), N > 0)
    {
        Matrix m = mat;
        vector<LL> result = m.pow(N) * v;
        printf("%d\n", (int) (result[(1 << S) - 1] % MOD));
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3420 Quad Tiling 题解 《挑战程序设计竞赛》