POJ3420 Quad Tiling DP + 矩阵快速幂 - c++编程基础

TOP

POJ3420 Quad Tiling DP + 矩阵快速幂

2015-07-20 17:59:42 来源: 作者: 【大中小】浏览:3次

题目大意是用1*2的骨牌堆积成4*N的矩形，一共有多少种方法，N不超过10^9。

这题和曾经在庞果网上做过的一道木块砌墙几乎一样。因为骨牌我们可以横着放，竖着放，我们假设以4为列，N为行这样去看，并且在骨牌覆盖的位置上置1，所以一共最多有16种状态。我们在第M行放骨牌的时候，第M+1行的状态也是有可能被改变的，设S(i,j)表示某一行状态为i时，将其铺满后下一行状态为j的方案书。考虑下如果我们让矩阵S和S相乘会有什么意义，考虑一下会发现S*S的意义当某行状态为i，接着其后面第2行的状态为j的可行方案数，一般地，S^n则代表接下来第n行状态为j的方案数，这里N很大，我们可以用快速幂对矩阵的幂进行加速。对于S矩阵的最初状态我们可以穷尽搜索来求。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include
              
                #include
               
                 using namespace std; int State[16][16]; int Start[16][16]; int IMod; void InitState(int ori, int s, int p) { bool isfull = true; for (int i = 0; i < 4; i++) { if (((s >> i) & 1) == 0) { //竖着放 InitState(ori, s | (1 << i), p | (1 << i)); //横着放 if (i < 3 && ((s >> (i + 1)) & 1) == 0) { int tp = s | (1 << i); tp |= (1 << (i + 1)); InitState(ori ,tp, p); } isfull = false; break; } } if (isfull) { State[ori][p] += 1; } } void Product(int a[][16], int b[][16], int res[][16]) { for (int i = 0; i < 16;i++) { for (int j = 0; j < 16; j++) { res[i][j] = 0; for (int k = 0; k < 16; k++) { res[i][j] += (a[i][k] * b[k][j] % IMod); res[i][j] %= IMod; } } } } void QProduct(int p[][16], int res[16][16], int n) { memset(res, 0, sizeof(int) * 16 * 16); int tmp[2][16][16]; int tmpres[16][16]; memcpy(tmp[0], p, sizeof(int) * 16 * 16); int i = 0; for (int k = 0; k < 16; k++) { res[k][k] = 1; } while (n) { if (n & 1) { memcpy(tmpres, res, sizeof(int) * 16 * 16); Product(tmpres, tmp[i & 1], res); } Product(tmp[i & 1], tmp[i & 1], tmp[(i + 1) & 1]); i++; n = n >> 1; } } int main() { #ifdef _DEBUG freopen("d:\\in.txt", "r", stdin); #endif int n, m; memset(State, 0, sizeof(State)); for (int i = 0; i < 16; i++) { InitState(i, i, 0); } int finstates[16][16]; int res[16][16]; memset(Start, 0, sizeof(Start)); Start[0][0] = 1; while (scanf("%d %d", &n, &m) != EOF) { if (n == 0 || m == 0) { break; } IMod = m; QProduct(State, finstates, n); Product(Start, finstates, res); int ans = 0; for (int i = 0; i < 16; i++) { ans += res[i][0]; ans %= IMod; } printf("%d\n", ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 4907 Task schedule	下一篇：poj2777--Count Color(线段树，二..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: