引言：轮廓线是指某一特定轮廓的状态，而不是某一行或某一列。
假设放置的是第放置骨牌的约定：（保证放置有最优子结构）行的骨牌，有三种方式：灰色是已经有的骨牌，绿色是新放置的骨牌。 各个配置方法如下解释，将第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=minn，m )。
voidDFSintx，int y，int col ) if col==k ) ) { d[y][x]=1； 返回； }DFSx1，) y1 )|1，col 1)； DFS ) x1 )|1，y1，col 1)； ifcol 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； voidDFSintx，int y，int col ) if col==k ) ) { d[y][x]=1； 返回； }DFSx1，) y1 )|1，col 1)； DFS ) x1 )|1，y1，col 1)； ifcol 2=k ) DFS ) x2 )|3，) y2 )|3，col2)； }voidmulinta[maxn]，intb ) [maxn]，intc ) [maxn] ) for ) intI=0； 国际航空； I ) forintj=0； 全部； j ) c ) I ) ) j )=0； } } LL t； forintI=0； 国际航空； I ) forintj=0； 全部； j ) if ！ a [ I ] [ j ] 连续； forintk=0； 呼叫； k ) if ) b[j][k] ) t=) ll ) a[i][j]*b[j][k]； t=c[i][k]； c[i][k]=t%mod； }}}}voidcpyinta[][maxn]，int b[][maxn] ) forintI=0； 国际航空； I ) forintj=0； 全部； j a I ) ) j )=b I ) ) j； }
}}void Eint a[][maxn]){ forint i=0;i<ALL;i++){ a[i][i]=1; forint 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); dfs0,0,0); ALL=1<<K; Ee); whilen>0){ ifn&1) { mule,d,tmp); cpye,tmp); } muld,d,tmp); cpyd,tmp); n>>=1; } printf”%d\n”,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 initint cur){ memsetp[cur],-1,sizeof p[cur]); tail[cur]=0;}int main){ int n,m,cur,st,pos,nst,hi; LL cnt; whilescanf”%d%d”,&m,&n)!=EOF){ ifm>n) swapm,n); cur=0; st = 1<<m)-1; hi = 1<<m-1); initcur); p[0][st]=tail[cur]; pos = tail[cur]++; cnt = 1; q[cur][pos]=mpst,cnt); forint i=0;i<n;i++){ forint j=0;j<m;j++,cur^=1){ initcur^1); forint k=tail[cur]-1;k>=0;k–){ st = q[cur][k].FF; cnt = q[cur][k].SS; ifst & hi){ nst = st^hi)<<1; ifpos=p[cur^1][nst])==-1){ pos = tail[cur^1]++; p[cur^1][nst] = pos; q[cur^1][pos]=mpnst,cnt); }else{ q[cur^1][pos].SS += cnt; } ifj && !st&1)){ nst = st^hi)<<1)|3; ifpos=p[cur^1][nst])==-1){ pos = tail[cur^1]++; p[cur^1][nst] = pos; q[cur^1][pos]=mpnst,cnt); }else{ q[cur^1][pos].SS += cnt; } } }else{ nst = st<<1)|1; ifpos=p[cur^1][nst])==-1){ pos = tail[cur^1]++; p[cur^1][nst] = pos; q[cur^1][pos]=mpnst,cnt); }else{ q[cur^1][pos].SS += cnt; } } } } } st = 1<<m)-1; pos = p[cur][st]; cnt = q[cur][pos].SS; printf”%lld\n”,cnt); } return 0;}
对于更复杂的插头DP问题后面再讨论