hihocoder 1048

题意：在一个N×M的格子里，现在有两种类型的砖块，1×2和2×1，问一共有多少种方案，可以将整个N×M的空间都填满。2<=N<=1000, 3<=m<=5。

思路：参考博客：http://blog.csdn.net/lu597203933/article/details/44137277

（事实上考虑的时候顺序是这样的1⃣️👉4⃣️👉3⃣️👉2⃣️）

1⃣️确定0表示什么，1表示什么。

在位置(i, j)如果我们选择横着贴砖，那么将(i, j),(i, j+1)都填写成1，如果竖着贴砖，我们将(i,j)填写成0，将(i+1, j)填写成1。

为什么这样表示呢？

首先确定有几种情况：

假如现在我们在铺砖位置(i, j), 并且假设之前的位置已经铺设好的了，在这个位置，我们的选择：

1.不用铺了，(i-1,j)竖着铺好了，那就继续看(i,j+1)；

2.横着铺，(i,j)和(i,j+1)都铺上；

3.竖着铺，(i,j)和(i+1,j)都铺上；

那么为什么竖着铺的时候(i,j)填写成0，(i+1, j)填写成1呢？

假设反过来，会造成什么结果呢？

如果某一位是0，那么你就看上一块是不是1即可；如果某一位是1，要检查右边那块是不是1，如果不是1，说明是竖着放的，向右继续检查，如果是1，说明可能是横着放的也有可能是竖着放的，假设是横着放的，那要判断右边那块的上面一块是不是1，但是这里就出现矛盾了，这里的1，到底是指竖着放的的一块呢还是指横着放的某一块呢？

所以要把(i,j)填写成0，(i+1, j)填写成1。

还有另一种解释：横着放设为1表示对下一行没有任何影响了，竖着放的第一块，对下面是有影响的，所以为0，第二块则是没有影响的，为1。

这样选择还有一个好处：在处理最后一行的时候，可以保证最后一行都是1， 因为最后一行绝对不能成为竖砖开始，所以很容易取得最后的解。

2⃣️确定第一行的合法状态。

枚举所有状态，对于每个状态的每一列进行判断。

如果某一位是0，就继续向右检查；

如果某一位是1，这时是不可能作为竖着放的第二块的，只可能是横着放的，那么就检查右边那块是不是1，这里注意不要越界，如果是1，就j- -，否则就不合法。（这里的判断的(i,x)一定不是由(i,x-1)位横着铺砖过来的，否则直接x=x+2,就不会来判断(i,x)位了）

注意⚠️：判断某一位是0还是1时，要注意如果是1的话结果应该是>0而不是1本身，因为这一位是有权值的。

void test1()
{
    for(int i=0;i<(1<<m);i++)
    {
        int sign=0;
        for(int j=m-1;j>=0&&sign==0;j--)
        {
            if(((1<<j)&i)>0)//该位是1,则后一块也得是1,第一行的1只能是横着放的
            {
                if(j==0)sign++;
                else if(((1<<(j-1))&i)==0)sign++;
                else j--;
            }
        }
        if(sign==0)dp[1][i]=1;
    }
}

3⃣️动态规划。

dp(i)(j):推到第i行状态为j时的方法数。

dp(i)(j)=sum{dp(i-1)(k),0<=k<(1<<m)&&k和j是可以兼容的}

判断是否兼容：

如果某一位是0，那么上一块只能是1；

如果某一位是1，那么就分两种情况：

上一块是0，那么继续向右检测；

上一块是1，那么就说明这里是横着铺的，右边一块也一定是1，右边一块的上一块一定是1，因为右边一块已经确定状态是横着铺了，如果都满足的话，就j- -，否则就说明不兼容。

bool judge(int x,int y)//x:这一行的状态，y:上一行的状态
{
    for(int i=m-1;i>=0;i--)
    {
        if(((1<<i)&x)==0)//该位是0，则上一块只能是1
        {
            if(((1<<i)&y)==0)
                return false;
        }
        else//该位是1
        {
            if(((1<<i)&y)>0)//如果上一块是0,就继续检测；如果上一块是1,(i,x+1)也一定是1，****并且(i-1,x+1)一定是1!!!(注意！！！）
            {
                if(i==0)return false;
                else if(((1<<(i-1))&x)>0&&((1<<(i-1))&y)>0)
                    i--;
                else return false;
            }
        }
    }
    return true;
}

for(int i=2;i<=n;i++)//每一行
{
    for(int j=0;j<(1<<m);j++)//这一行的状态
    {
        for(int k=0;k<(1<<m);k++)//上一行的状态
        {
            if(judge(j,k))
                dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
        }
    }
}

4⃣️dp(n)((1<<m)-1)即为总方法数。

因为最后一行只能都为1。

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
long long dp[1100][(1<<5)+10];//在第i行状态为j时的方法数
//竖放的第一块是0，第二块是1
int m;
void test1()
{
    for(int i=0;i<(1<<m);i++)
    {
        //printf("i=%d:",i);
        int sign=0;
        /*for(int j=m-1;j>=0;j--)
            printf("%d",((1<<j)&i));*/
        for(int j=m-1;j>=0&&sign==0;j--)
        {
            if(((1<<j)&i)>0)//该位是1,则后一块也得是1,第一行的1只能是横着放的
                //这里是>0,注意！！！不一定是1呀！！！
            {
                if(j==0)sign++;
                else if(((1<<(j-1))&i)==0)sign++;
                else j--;
            }
        }
        if(sign==0)dp[1][i]=1;
        //printf(" %lld\n",dp[1][i]);
    }
    //printf("\n");
}
bool judge(int x,int y)//x:这一行的状态，y:上一行的状态
{
    for(int i=m-1;i>=0;i--)
    {
        if(((1<<i)&x)==0)//该位是0，则上一块只能是1
        {
            if(((1<<i)&y)==0)
                return false;
        }
        else//该位是1
        {
            if(((1<<i)&y)>0)//如果上一块是0,就继续检测；如果上一块是1,(i,x+1)也一定是1，****并且(i-1,x+1)一定是1!!!(注意！！！）
            {
                if(i==0)return false;
                else if(((1<<(i-1))&x)>0&&((1<<(i-1))&y)>0)
                    i--;
                else return false;
            }
        }
    }
    return true;
}
int main()
{
    int n;//m比较小
    scanf("%d%d",&n,&m);
    memset(dp,0,sizeof(dp));
    test1();//处理出第一行合法的情况
    for(int i=2;i<=n;i++)//每一行
    {
        for(int j=0;j<(1<<m);j++)//这一行的状态
        {
            for(int k=0;k<(1<<m);k++)//上一行的状态
            {
                if(judge(j,k))
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
            }
            //printf("dp[%d][%d]:%lld\n",i,j,dp[i][j]);
        }
    }
    printf("%lld\n",dp[n][(1<<m)-1]);//最后一行是不可能出现0的
    return 0;
}

这里用枚举+判断会有些慢…

所以可以直接生成合法的方案。

1⃣️0和1的表示如上一个方法。

2⃣️对于每一个位置，有三种放置方法。

不放（下放）：这时这个块为0，则上一块只能是1。

上放：这时这个块为1，则上一块只能是0。

横放：这时这个块为1，右边的块也为1，那么上面那块为1，右边的上面那块也为1。

然后从0开始构造即可。

int num;//兼容的方案数
int ok[50010][2];//ok[][0]:上一行的状态；ok[][1]：下一行的状态
void dfs(int c,int pre,int now)//构造出所有兼容模式:c（列数），pre（上一行的状态），pre（该行的状态）
{
    if(c>m)return;//防止横放越界的情况
    if(c==m)
    {
        ok[num][0]=pre;
        ok[num++][1]=now;
        return;
    }
    dfs(c+1,(pre<<1)|1,now<<1);//不放（即下放），为0，则上行为1
    dfs(c+1,pre<<1,(now<<1)|1);//上放，为1，则上行为0
    dfs(c+2,(pre<<2)|3,(now<<2)|3);//横放，为1，右边为1，上边为1，上边的右边为1
}

3⃣️动态规划。

long long dp[15][50010];//推到第i行兼容方式为j时方法数
memset(dp,0,sizeof(dp));
dp[0][(1<<m)-1]=1;//第一行不能上放，所以第0行不能有空的，只能为1
for(int i=1;i<=n;i++)
{
    for(int j=0;j<num;j++)
    {
        dp[i][ok[j][1]]+=dp[i-1][ok[j][0]];
    }
}

因为第一行不能上放，所以第0行不能有0，只能都是1。

dp(i)(j):推到第i行状态为j时的方法数。

dp(i)(j)=sum{dp(i-1)(k),0<=k<(1<<m)&&k和j是可以兼容的}。

4⃣️dp(n)((1<<m)-1)即为答案。

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
int m;
int num;//兼容的方案数
int ok[50010][2];//ok[][0]:上一行的状态；ok[][1]：下一行的状态
long long dp[15][50010];//推到第i行兼容方式为j时方法数
void dfs(int c,int pre,int now)//构造出所有兼容模式:c（列数），pre（上一行的状态），pre（该行的状态）
{
    if(c>m)return;//防止横放越界的情况
    if(c==m)
    {
        ok[num][0]=pre;
        ok[num++][1]=now;
        return;
    }
    dfs(c+1,(pre<<1)|1,now<<1);//不放（即下放），为0，则上行为1
    dfs(c+1,pre<<1,(now<<1)|1);//上放，为1，则上行为0
    dfs(c+2,(pre<<2)|3,(now<<2)|3);//横放，为1，右边为1，上边为1，上边的右边为1
}
int main()
{
    int n;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        num=0;
        dfs(0,0,0);
        //printf("%d\n",num);
        memset(dp,0,sizeof(dp));
        dp[0][(1<<m)-1]=1;//第一行不能上放，所以第0行不能有空的，只能为1
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<num;j++)
            {
                dp[i][ok[j][1]]+=dp[i-1][ok[j][0]];
            }
        }
        printf("%lld\n",dp[n][(1<<m)-1]);
    }
    return 0;
}

当n很大的时候，就不能用上述的方法算了，这个时候矩阵的优势就体现出来了。

51nod 1033

题意：2 <= m <= 10^9，2 <= n <= 5

思路：题目转化为求经过n次转化，从初始态到终态有几种转化法。

建立矩阵的方法：矩阵的大小为(1<<m-1) ，如果pre状态能到达状态now，那么mat(pre)(now)=1，然后求此矩阵的n次幂即可。

输出的是ans((1<<m)-1)((1<<m)-1)，因为第0行都为1，最后一行也都为1。

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
int m;
struct mat
{
    long long a[40][40];
}mt,r;
void dfs(int c,int pre,int now)//构造出所有兼容模式:c（列数），pre（上一行的状态），pre（该行的状态）
{
    if(c>m)return;//防止横放越界的情况
    if(c==m)
    {
        mt.a[pre][now]=1;
        return;
    }
    dfs(c+1,(pre<<1)|1,now<<1);//不放（即下放），为0，则上行为1
    dfs(c+1,pre<<1,(now<<1)|1);//上放，为1，则上行为0
    dfs(c+2,(pre<<2)|3,(now<<2)|3);//横放，为1，右边为1，上边为1，上边的右边为1
}
mat mult(mat x,mat y)
{
    mat res={0};
    int i,j,k;
    for(i=0;i<(1<<m);i++)
        for(j=0;j<(1<<m);j++)
            for(k=0;k<(1<<m);k++)
                res.a[i][j]=(res.a[i][j]+(x.a[i][k]*y.a[k][j])%MOD)%MOD;
    return res;
}
mat PowerMod(mat x,long long n)
{
    mat ans={0};
    int i;
    for(i=0;i<(1<<m);i++)
        ans.a[i][i]=1;
    while(n>0)
    {
        if(n%2==1)
            ans=mult(ans,x);
        x=mult(x,x);
        n=n/2;
    }
    return ans;
}
int main()
{
    long long n;
    scanf("%lld%d",&n,&m);
    memset(mt.a,0,sizeof(mt.a));
    dfs(0,0,0);
    r=PowerMod(mt,n);
    printf("%lld\n",r.a[(1<<m)-1][(1<<m)-1]);//第0行只能全是1
    return 0;
}