引言：轮廓线是指某一特定轮廓的状态，而不是某一行或某一列。
假设放置的是第放置骨牌的约定：（保证放置有最优子结构）行的骨牌，有三种方式：灰色是已经有的骨牌，绿色是新放置的骨牌。 各个配置方法如下解释，将第I行的状态设为x，将第i-1行的状态设为y。
如果第I行不放置，则必须有放置在前一行的骨牌。 与x对应的二进制比特为0，与y对应的二进制比特为1。 第I行竖放骨牌，前一行必须为空。 与x对应的二进制比特为1，与y对应的二进制比特为0。 第I行的横向骨牌在前一行必须有两个骨牌。 否则，就会出现空缺。 x对应于二进制位为1，y对应于二进制位为1。
简单示例：
tiling a网格with dominoes
3358 ACM.hdu.edu.cn/show problem.PHP？ pid=1992
将主板宽度限制为4，数据不超过int，只有长度22以内才能满足答案。
手写查找规则。
33558 www.cn blogs.com/lzsz 1212/archive/2012/05/02/2478839.html
如果不把这个作为更一般的问题来限制盘的宽度的话，
hihocoder米诺问题在窄棋盘(2￣min ) n，m (小于200 )的情况下，构造转移矩阵，研究了快速乘幂的求解方法。
33558 hiho coder.com/contest/hiho 43/problem/1
过渡矩阵构造法是，y为i-1行状态，x为I行状态，dfs构造为K^2的复杂度，k=min(n，m )。
voidDFS(intx，int y，int col ) if (col==k ) ) { d[y][x]=1； 返回； }DFS(x1，) y1 )|1，col 1)； DFS () x1 )|1，y1，col 1)； if(col 2=k ) DFS () x2 )|3，) y2 )|3，col2)； }
那么复杂度为k^3*logn，k=7时(2^7=128 )的计算效率是可以接受的。
# include cstdio # includeiostreamusingnamespacestd； 泰普德夫龙龙LL； 常数上限=17； 常数输入模式=12357； int d[maxn][maxn]； int K，ALL； voidDFS(intx，int y，int col ) if (col==k ) ) { d[y][x]=1； 返回； }DFS(x1，) y1 )|1，col 1)； DFS () x1 )|1，y1，col 1)； if(col 2=k ) DFS () x2 )|3，) y2 )|3，col2)； }voidmul(inta(([maxn]，intb ) [maxn]，intc ) [maxn] ) for ) intI=0； 国际航空； I ) for(intj=0； 全部； j ) (c ) I ) ) j )=0； } } LL t； for(intI=0； 国际航空； I ) for(intj=0； 全部； j () if (！ a [ I ] [ j ] (连续； for(intk=0； 呼叫； k () if ) b[j][k] ) t=) ll ) a[i][j]*b[j][k]； t=c[i][k]； c[i][k]=t%mod； }}}}voidcpy(inta[][maxn]，int b[][maxn] ) for(intI=0； 国际航空； I ) for(intj=0； 全部； j ((a (I ) ) j )=b (I ) ) j； }
}}void E(int a[][maxn]){ for(int i=0;i<ALL;i++){ a[i][i]=1; for(int j=i+1;j<ALL;j++){ a[i][j]=a[j][i]=0; } }}int e[maxn][maxn],tmp[maxn][maxn];int main(){// freopen("data.in","r",stdin); int n; scanf("%d%d",&K,&n); dfs(0,0,0); ALL=1<<K; E(e); while(n>0){ if(n&1) { mul(e,d,tmp); cpy(e,tmp); } mul(d,d,tmp); cpy(d,tmp); n>>=1; } printf("%dn",e[ALL-1][ALL-1]); return 0;}
uva11270同此题 ，大白书精讲，但是n*m<101，棋盘可能不是窄棋盘，k^3*logn矩阵运算会超时。
考虑到n<=10，可以构造2^n*n个转移方程，m轮递求解。
bfs可以避免访问不能求解的状态。状态st=k4k3k2k1k0，ki表示一个二进制位，有方块就为1，否则为0。
#include <cstdio>#include <iostream>#include <cstring>using namespace std;typedef long long LL;typedef LL type;typedef pair<int,LL> pil;#define mp make_pair#define FF first#define SS secondconst int maxn = 1<<10;int p[2][maxn];pil q[2][maxn];int tail[2];void init(int cur){ memset(p[cur],-1,sizeof p[cur]); tail[cur]=0;}int main(){ int n,m,cur,st,pos,nst,hi; LL cnt; while(scanf("%d%d",&m,&n)!=EOF){ if(m>n) swap(m,n); cur=0; st = (1<<m)-1; hi = 1<<(m-1); init(cur); p[0][st]=tail[cur]; pos = tail[cur]++; cnt = 1; q[cur][pos]=mp(st,cnt); for(int i=0;i<n;i++){ for(int j=0;j<m;j++,cur^=1){ init(cur^1); for(int k=tail[cur]-1;k>=0;k--){ st = q[cur][k].FF; cnt = q[cur][k].SS; if(st & hi){ nst = (st^hi)<<1; if((pos=p[cur^1][nst])==-1){ pos = tail[cur^1]++; p[cur^1][nst] = pos; q[cur^1][pos]=mp(nst,cnt); }else{ q[cur^1][pos].SS += cnt; } if(j && !(st&1)){ nst = ((st^hi)<<1)|3; if((pos=p[cur^1][nst])==-1){ pos = tail[cur^1]++; p[cur^1][nst] = pos; q[cur^1][pos]=mp(nst,cnt); }else{ q[cur^1][pos].SS += cnt; } } }else{ nst = (st<<1)|1; if((pos=p[cur^1][nst])==-1){ pos = tail[cur^1]++; p[cur^1][nst] = pos; q[cur^1][pos]=mp(nst,cnt); }else{ q[cur^1][pos].SS += cnt; } } } } } st = (1<<m)-1; pos = p[cur][st]; cnt = q[cur][pos].SS; printf("%lldn",cnt); } return 0;}
对于更复杂的插头DP问题后面再讨论