Zju1100 Mondriaan

谁践踏了优雅 2021-12-24 16:25 158阅读 0赞

## 题目描述 ##

### 有一个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^M^2=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) ###

转载于:https://www.cnblogs.com/akura/p/10896522.html