Magetz-用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果-用C语言实现的算法

共享中心

其它软件使用

xmind

Android

HTML

PHP

Nginx

安装

Mysql

Linux

Python 语言

R语言

AI智能

算法学习知识培训

AI资讯

用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果
时间：2016-09-02 18:07:20

用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果

我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n- 1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态 111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110-& gt;111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。

后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。

经典题目10

POJ2778

题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。

下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A 结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。

题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。

#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;
class CMatrix
{
    public:
    long element[MAX_SIZE][MAX_SIZE];
    void setSize(int);
    void setModulo(int);
    CMatrix operator* (CMatrix);
    CMatrix power(int);
    private:
    int size;
    long modulo;
};
void CMatrix::setSize(int a)
{
    for (int i=0; i<a; i++)
    for (int j=0; j<a; j++)
    element[i][j]=0;
    size = a;
}
void CMatrix::setModulo(int a)
{
    modulo = a;
}
CMatrix CMatrix::operator* (CMatrix param)
{
    CMatrix product;
    product.setSize(size);
    product.setModulo(modulo);
    for (int i=0; i<size; i++)
        for (int j=0; j<size; j++)
            for (int k=0; k<size; k++)
            {
                product.element[i][j]+=element[i][k]*param.element[k][j];
                product.element[i][j]%=modulo;
            }
    return product;
}
CMatrix CMatrix::power(int exp)
{
    CMatrix tmp=(*this)*(*this);
    if (exp==1) return *this;
    else if (exp&1) return tmp.power(exp/2)*(*this);
          else return tmp.power(exp/2);
}
int main()
{
    const int validSet[]={0,3,6,12,15,24,27,30};
    long n, m, p;
    CMatrix unit;
    scanf("%d%d%d", &n, &m, &p);
    unit.setSize(SIZE);
    for (int i=0; i<SIZE; i++)
        for (int j=0; j<SIZE; j++)
        if (((~i)&j) == ((~i)&(SIZE-1)))
        {
            bool isValid=false;
            for (int k=0;k<8;k++) isValid=isValid||(i&j)==validSet[k];
            unit.element[i][j]=isValid;
        }
    unit.setModulo(p);
    printf("%d",unit.power(n).element[SIZE-1][SIZE-1] );
    return 0;
}

共享中心

问题知识列表