Zju1100 Mondriaan

题目描述

有一个m行n列的矩阵，用1*2的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？你只需要求出覆盖方法总数mod p的值即可。

输入格式

三个整数数n,m,p，m<=5，p<=10000，n<=10000

输出格式

一个整数：总数模p的结果

不难想到可以用状压来做这题。设dp(i,j)表示第i列放置情况为j的二进制表示，其中j的第k位为1时表示这玩意是一块竖着的骨牌的上半部分，为0则是其余的情况。我们考虑一下dp(i,j)可以由哪些状态转移而来。

设上一行的二进制表示为j，当前一行的为k。由于当j的某些位置为1时，k的这些位置也必须为1。为了在满足我们的定义的同时把j的1给转移下来，我们可以将j和k做一次按位或运算。此时数j|k中为0的部分就是放横着的骨牌的地方。显然j|k中为0的连续部分长度必须是偶数。所以我们转移的第一个条件就是：

1.j|k的每一段连续0的长度都必须为偶数

如果上一行的某一位是1，而当前一行的这一位也是1，那么不合法，不能转移。所以我们的第二个转移的条件就是：

2.j和k的相同位置不能都为1

怎么判断两个条件呢？

对于第二个条件，我们可以将j和k做一次按位与运算，如果得到的数不为0，即得到的数里面含有1，那么不合法：

if(j&k) continue;

对于第一个条件，我们只好O(m)地慢慢转移：

int odd=0,cnt=0;

for(register int l=0;l<m;l++)

	if((j|k)>>l&1) odd|=cnt,cnt=0;

	else cnt^=1;

if(odd|cnt) continue;

所以我们得到了一个时间复杂度为O(NM * 2^M * 2^M)=O(NM * 4^M)的算法。

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxm 5

#define maxn 10001

using namespace std;

int dp[maxn][1<<maxm];

int n,m,p;

inline int read(){

    register int x(0),f(1); register char c(getchar());

    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

int main(){

    n=read(),m=read(),p=read();

    dp[0][0]=1;

    for(register int i=1;i<=n;i++){

        for(register int j=0;j<1<<m;j++){

            for(register int k=0;k<1<<m;k++){

                if(j&k) continue;

                int odd=0,cnt=0;

                for(register int l=0;l<m;l++)

                    if((j|k)>>l&1) odd|=cnt,cnt=0;

                    else cnt^=1;

                if(odd|cnt) continue;

                (dp[i][j]+=dp[i-1][k])%=p;

            }

        }

    }

    printf("%d\n",dp[n][0]);

    return 0;

}

这个复杂度足够通过本题了。

对于这个算法有个小小的优化：

设函数f(j,k)=j|k，不难发现其定义域大小为2^M2=4^{M而值域大小只有2}M，所以我们对于一个f(j,k)其实重复算了2^M次。所以我们可以预处理出所有f(j,k)：

for(register int i=0;i<1<<m;i++){

    int odd=0,cnt=0;

    for(register int j=0;j<m;j++)

        if(i>>j&1) odd|=cnt,cnt=0;

        else cnt^=1;

    even[i]=odd|cnt?0:1;

}

然后在dp的过程中：

dp[0][0]=1;

for(register int i=1;i<=n;i++){

    for(register int j=0;j<1<<m;j++){

        for(register int k=0;k<1<<m;k++){

            if(!(j&k)&&even[j|k]) (dp[i][j]+=dp[i-1][k])%=p;

        }

    }

}

可以把时间复杂度优化成O(N * 4^M+M * 2^M)

巴特西

Zju1100 Mondriaan

题目描述

有一个m行n列的矩阵，用1*2的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？你只需要求出覆盖方法总数mod p的值即可。

输入格式

三个整数数n,m,p，m<=5，p<=10000，n<=10000

输出格式

一个整数：总数模p的结果

不难想到可以用状压来做这题。设dp(i,j)表示第i列放置情况为j的二进制表示，其中j的第k位为1时表示这玩意是一块竖着的骨牌的上半部分，为0则是其余的情况。我们考虑一下dp(i,j)可以由哪些状态转移而来。

1.j|k的每一段连续0的长度都必须为偶数

如果上一行的某一位是1，而当前一行的这一位也是1，那么不合法，不能转移。所以我们的第二个转移的条件就是：

2.j和k的相同位置不能都为1

怎么判断两个条件呢？

对于第二个条件，我们可以将j和k做一次按位与运算，如果得到的数不为0，即得到的数里面含有1，那么不合法：

对于第一个条件，我们只好O(m)地慢慢转移：

所以我们得到了一个时间复杂度为O(NM * 2^M * 2^M)=O(NM * 4^M)的算法。

这个复杂度足够通过本题了。

对于这个算法有个小小的优化：

设函数f(j,k)=j|k，不难发现其定义域大小为2^M2=4^{M而值域大小只有2}M，所以我们对于一个f(j,k)其实重复算了2^M次。所以我们可以预处理出所有f(j,k)：

然后在dp的过程中：

可以把时间复杂度优化成O(N * 4^M+M * 2^M)

最新文章

热门文章

巴特西

Zju1100 Mondriaan

题目描述

有一个m行n列的矩阵，用1*2的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？ 你只需要求出覆盖方法总数mod p的值即可。

输入格式

三个整数数n,m,p，m<=5，p<=10000，n<=10000

输出格式

一个整数：总数模p的结果

不难想到可以用状压来做这题。设dp(i,j)表示第i列放置情况为j的二进制表示，其中j的第k位为1时表示这玩意是一块竖着的骨牌的上半部分，为0则是其余的情况。我们考虑一下dp(i,j)可以由哪些状态转移而来。

1.j|k的每一段连续0的长度都必须为偶数

如果上一行的某一位是1，而当前一行的这一位也是1，那么不合法，不能转移。所以我们的第二个转移的条件就是：

2.j和k的相同位置不能都为1

怎么判断两个条件呢？

对于第二个条件，我们可以将j和k做一次按位与运算，如果得到的数不为0，即得到的数里面含有1，那么不合法：

对于第一个条件，我们只好O(m)地慢慢转移：

所以我们得到了一个时间复杂度为O(NM * 2^M * 2^M)=O(NM * 4^M)的算法。

这个复杂度足够通过本题了。

对于这个算法有个小小的优化：

设函数f(j,k)=j|k，不难发现其定义域大小为2M2=4M而值域大小只有2M，所以我们对于一个f(j,k)其实重复算了2^M次。所以我们可以预处理出所有f(j,k)：

然后在dp的过程中：

可以把时间复杂度优化成O(N * 4^M+M * 2^M)

最新文章

热门文章

有一个m行n列的矩阵，用1*2的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？你只需要求出覆盖方法总数mod p的值即可。

设函数f(j,k)=j|k，不难发现其定义域大小为2^M2=4^{M而值域大小只有2}M，所以我们对于一个f(j,k)其实重复算了2^M次。所以我们可以预处理出所有f(j,k)：