文章目录

hiho1143 && hiho 1151&&1033 骨牌覆盖 V2

骨牌覆盖问题

问题描述

在 m ∗ n m*n m∗n的一个长方形方格中，用一个1*2的骨牌排满方格。问有多少种不同的排列方法。 ( n &lt; = 5 ) (n &lt;= 5) (n<=5)

题目

2个数M N，中间用空格分隔 2 &lt; = m &lt; = 1 0 9 ， 2 &lt; = n &lt; = 5 2 &lt;= m &lt;= 10^9，2 &lt;= n &lt;= 5 2<=m<=109，2<=n<=5

输出数量 Mod 10^9 + 7

输入
2 3
输出
3

分析：

注意到n比较小，m比较大，我们可以用dp状压+矩阵快速幂解这道题
通过状态压缩构建转移矩阵，通过矩阵快速幂加速计算。

状态压缩

每一个行用一个二进制数表示：N位二进制数表示一个状态，其中第k位为1表示第k列是一个竖着的1*2长方形上面的一般，第k位为0表示其他情况

状态 j j j可以转化为 k k k状态当且仅当(即假设 j j j状态合法，下面为 k k k状态同样合法)：

  • j和k按位运算为0
  • j和k按位或运算的结果中，连续的0都是偶数个

POJ2411
具体问题还是看代码吧，

参考代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 13;
const int mod = 1e9+7;
int n,m;
LL f[12][1<<11];
bool in_s[1<<11];

struct Matrix{
  #define maxn 100
  int n,m;
  Matrix(int nn = 1,int mm = 1):n(nn),m(mm){ memset(a,0,sizeof(a));};
  long long a[maxn][maxn];
};
void print(const Matrix &a)
{
 for(int i = 1;i <= a.n; ++i,cout<<endl)
  for(int j= 1;j <= a.m; ++j)
     cout<<a.a[i][j]<<" ";
}
Matrix operator*(Matrix a,Matrix b)
{
  assert(a.m == b.n);
  Matrix c(a.n,b.m);
  for(int i = 1;i <= a.n; ++i)
  {
    for(int j = 1;j <= b.m; ++j)
    {
      for(int k = 1;k <= a.m; ++k)
      {
        c.a[i][j] += a.a[i][k] * b.a[k][j];
        c.a[i][j] %= mod;
      }
    }
  }
// print(c);
  return c;
}
Matrix B;
void solve(int m){
  for(int i = 0;i < (1<<m); ++i){
    bool cnt = 0,has_odd = 0;
    for(int j = 0;j < m; ++j){
      if(i >>j &1) has_odd |= cnt,cnt = 0;
      else cnt^= 1;
      in_s[i] = has_odd |cnt?0:1;
    }

  }

  // f[0][0] = 1;
  // for(int i = 1;i <= n; ++i){
    for(int j = 0;j < (1<<m); ++j){
      // f[i][j] = 0;
      for(int k = 0;k < (1<<m); ++k){
        if((j&k) == 0&& in_s[j|k])
             B.a[j+1][k+1] = 1;
           // f[i][j] += f[i-1][k];
      // }
    }
  }
  // print(B);
  // cout<<f[n][0]<<endl;
}


LL M,N;
int main(void){
  scanf("%lld%lld",&M,&N);
  B.n = B.m = 1<<N;
  solve(N);
  Matrix ans(1,1<<N);

  ans.a[1][1] = 1;
  // print(ans);
  // cout<<endl;
  // print(B);
  while(M > 0){
    if(M & 1) 
      ans = ans*B;
    B = B*B;
    // cout<<endl;
    // print(B);
    M >>= 1;
  }
  cout<<ans.a[1][1]<<endl;

  return 0;
}