hihocoder第42周 k*N骨牌覆盖（状态dp+矩阵快速幂）

上周的3*N的骨牌，因为状态只有8中，所以我们可以手算出状态转移的矩阵

但是这周是k*N，状态矩阵不好手算，都是我们改成用程序自动生成一个状态转移的矩阵就行了，然后用这个矩阵进行快速幂即可

枚举枚举上下两行的状态，然后判断上一行的状态能不能转移为这一行的状态

如果上一行的某个位置为0，那么这一行的该位置必须为1

如果上一行的某个位置为1，那么这一行的该位置可以为0

如果上一行的某个位置为1，且这一行的该位置为1，那么上下两行该位置相邻的位置也得为1

根据这三条规则判断状态能不能转移成功，然后生成矩阵

因为状态矩阵很大，不能够开成局部变量，所以一律开成全局的，函数的返回值全部改成void

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 #include <string>
 12 #include <math.h>
 13 using namespace std;
 14 #pragma warning(disable:4996)
 15 typedef long long LL;
 16 const int INF = 1 << 30;
 17 const int MOD = 12357;
 18 const int N = 1 << 8;
 19 int n, k;
 20 struct Matrix
 21 {
 22     int mat[N][N];
 23     void makeUnit()
 24     {
 25         int m = (1 << k);
 26         for (int i = 0; i < m; ++i)
 27         {
 28             for (int j = 0; j < m; ++j)
 29                 mat[i][j] = (i == j);
 30         }
 31     }
 32     void makeZero()
 33     {
 34         int m = 1 << k;
 35         for (int i = 0; i < m; ++i)
 36         {
 37             for (int j = 0; j < m; ++j)
 38                 mat[i][j] = 0;
 39         }
 40     }
 41 }a, ret1, ret2;
 42 void copy(Matrix &des, const Matrix &s)
 43 {
 44     int m = 1 << k;
 45     for (int i = 0; i < m; ++i)
 46     {
 47         for (int j = 0; j < m; ++j)
 48             des.mat[i][j] = s.mat[i][j];
 49     }
 50 }
 51 void dfs(int x, int y, int col)//这个题目提示的矩阵生成方法，挺厉害的
 52 {
 53     if (col == k)
 54     {
 55         a.mat[y][x] = 1;
 56         return;
 57     }
 58     dfs(x << 1, y << 1 | 1, col + 1);
 59     dfs(x << 1 | 1, y << 1, col + 1);
 60     if (col + 2 <= k)
 61         dfs((x << 2) + 3, (y << 2) + 3, col + 2);
 62 }
 63 void multiply(const Matrix &lhs, const Matrix &rhs)
 64 {
 65     ret2.makeZero();
 66     int m = 1 << k;
 67     for (int z = 0; z < m; ++z)
 68     {
 69         for (int i = 0; i < m; ++i)
 70         {
 71             if (lhs.mat[i][z] == 0) continue;
 72             for (int j = 0; j < m; ++j)
 73             {
 74                 ret2.mat[i][j] += lhs.mat[i][z] * rhs.mat[z][j];
 75                 if (ret2.mat[i][j] >= MOD)
 76                     ret2.mat[i][j] %= MOD;
 77             }
 78         }
 79     }
 80 }
 81 void pow(Matrix a, int t)
 82 {
 83     ret1.makeUnit();
 84     while (t)
 85     {
 86         if (t & 1)
 87         {
 88             multiply(ret1, a);
 89             copy(ret1, ret2);
 90         }
 91         t >>= 1;
 92         multiply(a, a);
 93         copy(a, ret2);
 94     }
 95 }
 96 bool check(int x, int y)
 97 {
 98     int m = 1 << k-1;
 99     while (m)
100     {
101         if ((x & 1) == 0 && (y & 1) == 1)
102         {
103             x >>= 1;
104             y >>= 1;
105             m >>= 1;
106         }
107         else if ((x & 1) == 1 && (y & 1) == 0)
108         {
109             x >>= 1;
110             y >>= 1;
111             m >>= 1;
112         }
113         else if ((x & 1) == 1 && (y & 1) == 1)
114         {
115             x >>= 1;
116             y >>= 1;
117             if ((x & 1) == 1 && (y & 1) == 1)
118             {
119                 x >>= 1;
120                 y >>= 1;
121                 m >>= 2;
122             }
123             else
124                 return false;
125         }
126         else
127             return false;
128     }
129     return true;
130 }
131 void makeMatrix()
132 {
133     int m = 1 << k;
134     for (int i = 0; i < m; ++i)
135     {
136         for (int j = 0; j < m; ++j)
137         {
138             if (check(i, j))
139                 a.mat[i][j] = 1;
140         }
141     }
142 }
143 int main()
144 {
145     scanf("%d%d", &k, &n);
146     a.makeZero();
147     //dfs(0, 0, 0);
148     makeMatrix();
149     pow(a, n);
150     int m = (1 << k) - 1;
151     printf("%d
", ret1.mat[m][m]);
152     return 0;
153 }

View Code