题解
这题是一道非常好的插头题，与一般的按格转移的题目不同，由于m很大，要矩阵乘法，这题需要你做一个按列转移的插头DP。
按列转移多少与按格转移不同，但大体上还是基于连通性进行转移。每一列只有右插头是对下一列的转移有影响的，那么我们只需要记录每一列的右插头的连通情况，用最小表示法表示为当前列的状态。在转移的时候，我们只知道上一列的右插头，即本列的左插头的情况，而上插头还需要自己记一个标记。
那么我们具体分析：
1、不存在上插头
1、同时存在左插头和右插头，不需要修改当前插头，直接把上一列的右插头当做当前列的右插头
2、只在左插头，即从上一列的某一个连通块转移过来，记录连通块。（左下插头）
3、只在右插头，即此为一个新的连通块，打上标记，表明这是一个新的连通块。（右下插头）
2、存在上插头
1、同时存在左插头和右插头，一个格子里有三个插头，非法状态
2、都不存在左插头和右插头，不需要修改当前插头，即从上往下。
3、存在左插头
1、上插头和左插头同属一个连通块，但不在最终状态（没有右插头）的右下角的格子里出现，非法状态
2、上插头是左下插头，合并连通块，并删除这两个插头（这个合并比较特殊，因为两个都是已知的连通块，具体画图比较清晰）
3、上插头是右下插头，合并连通块，删掉当前插头
4、不存在左插头
1、上插头是左下插头，合并连通块，删除左下插头
2、上插头是右下插头，合并为新的连通块
具体情况还是自己动手画图比较清晰。
然后就到了矩乘的部分。首先考虑构造矩阵，g[i][j] = 1表示i状态能推到j状态，因此我们只需要枚举这些状态，一个一个判转移就可以了。
初始的情况下，只存在全空的状态和0和N-1有插头的情况，因此答案就是矩阵快速幂后的ans[1][0]，即从初始状态推向终止状态。
程序
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 #include <iostream> 7 8 using namespace std; 9 10 typedef long long LL; 11 12 const int HASH = 419; 13 const int STATE = 1010; 14 const int MAXD = 15; 15 const int MOD = 7777777; 16 int N, M; 17 int code[MAXD], ch[MAXD]; 18 int g[200][200], D; 19 20 struct HASHMAP 21 { 22 int head[HASH], state[STATE], next[STATE], size; 23 void clear() 24 { 25 size = 0; 26 memset(head, -1, sizeof(head)); 27 } 28 int push(int st) 29 { 30 int i, x = st%HASH; 31 for (i = head[x]; i != -1; i = next[i]) 32 if (st == state[i]) 33 return i; 34 state[size] = st; 35 next[size] = head[x]; 36 head[x] = size++; 37 return size-1; 38 } 39 }hm; 40 41 void decode(int *code, int n, int st) 42 { 43 int i; 44 for (i = n-1; i >= 0; --i) 45 { 46 code[i] = st&3; 47 st >>= 2; 48 } 49 } 50 51 int encode(int *code, int n) 52 { 53 int i, st = 0, cnt = 0; 54 memset(ch, -1, sizeof(ch)); 55 ch[0] = 0; 56 for (int i = 0; i < n; ++i) 57 { 58 if (ch[code[i]] == -1) 59 ch[code[i]] = ++cnt; 60 code[i] = ch[code[i]]; 61 st <<= 2; 62 st |= code[i]; 63 } 64 return st; 65 } 66 67 bool check(int st, int nst) 68 { 69 decode(code, N, st); 70 int i, j, k, flag = 0, cnt = 0; 71 for (i = 0; i < N; ++i) 72 { 73 if (flag == 0) 74 { 75 if (!code[i] && !(nst&(1<<i))) 76 return false; 77 if (code[i] && (nst&(1<<i))) 78 continue ; 79 if (code[i]) 80 flag = code[i]; 81 else 82 flag = -1; 83 k = i; 84 } 85 else 86 { 87 if (code[i] && (nst&(1<<i))) 88 return false; 89 if (!code[i] && !(nst&(1<<i))) 90 continue ; 91 if (code[i]) 92 { 93 if (code[i] == flag && !(nst&(1<<i)) && (nst != 0 || i != N-1)) 94 return false; 95 if (flag > 0) 96 { 97 for (j = 0; j < N; ++j) 98 if (code[j] == code[i] && j != i) 99 code[j] = code[k]; 100 code[i] = code[k] = 0; 101 } 102 else 103 { 104 code[k] = code[i]; 105 code[i] = 0; 106 } 107 } 108 else 109 { 110 if (flag > 0) 111 { 112 code[i] = code[k]; 113 code[k] = 0; 114 } 115 else 116 { 117 code[k] = code[i] = N+(++cnt); 118 } 119 } 120 flag = 0; 121 } 122 } 123 if (flag != 0) 124 return false; 125 return true; 126 } 127 128 struct Node 129 { 130 int g[200][200]; 131 int D; 132 }node[20]; 133 134 void init() 135 { 136 if (node[N].D != 0) 137 { 138 memcpy(g, node[N].g, sizeof(node[N].g)); 139 D = node[N].D; 140 return ; 141 } 142 hm.clear(); 143 hm.push(0); 144 memset(code, 0, sizeof(code)); 145 code[0] = code[N-1] = 1; 146 hm.push(encode(code, N)); 147 int i, j, st, nst; 148 memset(g, 0, sizeof(g)); 149 for (i = 1; i < hm.size; ++i) 150 { 151 st = hm.state[i]; 152 for (nst = 0; nst < (1<<N); ++nst) 153 if (check(st, nst)) 154 { 155 j = hm.push(encode(code, N)); 156 g[i][j] = 1; 157 } 158 } 159 D = hm.size; 160 node[N].D = D; 161 memcpy(node[N].g, g, sizeof(g)); 162 } 163 164 struct Matrix 165 { 166 int mat[200][200]; 167 int n, m; 168 friend Matrix operator * (const Matrix &AI, const Matrix &BI) 169 { 170 Matrix ret; 171 ret.n = AI.n, ret.m = BI.m; 172 int i, j, k; 173 LL sum; 174 for (i = 0; i < ret.n; ++i) 175 for (j = 0; j < ret.m; ++j) 176 { 177 sum = 0; 178 for (k = 0; k < ret.n; ++k) 179 sum += (LL)AI.mat[i][k]*BI.mat[k][j]; 180 ret.mat[i][j] = sum%MOD; 181 } 182 return ret; 183 } 184 Matrix power(int num) 185 { 186 Matrix ret; 187 ret.n = n, ret.m = m; 188 int i, j; 189 memset(ret.mat, 0, sizeof(ret.mat)); 190 for (i = 0; i < n; ++i) 191 ret.mat[i][i] = 1; 192 Matrix temp = *this; 193 while (num > 0) 194 { 195 if (num&1) 196 ret = ret*temp; 197 temp = temp*temp; 198 num >>= 1; 199 } 200 memcpy(mat, ret.mat, sizeof(ret.mat)); 201 } 202 }; 203 204 void work() 205 { 206 Matrix ans; 207 ans.n = ans.m = D; 208 memcpy(ans.mat, g, sizeof(g)); 209 ans.power(M); 210 if (ans.mat[1][0] == 0) 211 printf("Impossible\n"); 212 else 213 printf("%d\n", ans.mat[1][0]%MOD); 214 } 215 216 int main() 217 { 218 int i; 219 for (i = 0; i < 20; ++i) 220 node[i].D = 0; 221 while (~scanf("%d %d", &N, &M)) 222 { 223 init(); 224 work(); 225 } 226 return 0; 227 } 228
ZOJ 3256 Tour in the Castle 插头DP 矩阵乘法
原文：http://www.cnblogs.com/-ZZB-/p/6441355.html