某天，wangjy和DaoThree在玩多米诺游戏。。。 　　DaoThree提出一个令wangjy抓头的问题： 　　有一个m行n列的矩阵，用1*2的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？ 　　请你帮助wangjy解决:) 　　wangjy不想看到长串的高精度数，你只需要求出覆盖方法总数mod p 的值即可。 Input (domino.in) 　　三个整数数n,m,p Output (domino.out) 　　一个整数：总数模p的结果 Sample Input 　　7 2 10 Sample Output 　　1 对样例的说明： 　　总共有21种方法 约定 　　m<=5 　　p<=10000 　　50%的数据n<=10 　　100%的数据n<=10000

因为M只有5,可以用二进制数表示每一列的状态,0表示平直的,1表示凸出的

图例:
　　__
___|....|
......|....|

0    1  
在一个铺好的图形中,第i行和第i+1行的图案可以用x,y两个数表示,我们可以定义x,y相对应.y在i+1,x在i.若y的对应数是x1,x2 ,x3.....xn

则方程可以是f[i+1,y]=f[i,x1]+f[i,x2]+f[i,x3]+....+f[i,xn];

x和y的所有对应关系可以用搜索出来

program jk_domino;
var n,m,p,te,i,j:longint;
    a:array[1..1000,1..2] of longint;
    f:array[0..10000,0..32] of longint;

procedure doit(k,x,y:longint);
begin
    if k>m then exit;
    if k=m then
      begin
        inc(te);
        a[te,1]:=x; a[te,2]:=y;
        exit;
      end;
    doit(k+2,x shl 2,y shl 2);{连续在两层放上横的骨牌}
    doit(k+1,x shl 1,(y shl 1)or 1);｛一层竖着放｝
    doit(k+1,(x shl 1)or 1,y shl 1);　｛另一层竖着放｝
end;

begin
readln(n,m,p);
te:=0;
doit(0,0,0);
f[0,0]:=1;
for i:=1 to n do
for j:=1 to te do
f[i,a[j,2]]:=(f[i,a[j,2]]+f[i-1,a[j,1]]) mod p;

writeln(f[n,0] mod p);
end.

搜索构造过程中的三种情况分别是
1:
.__
|__|
|__|

0 0
0 0

y shl 2
x shl 2

2:
_____
__| .. |
__|__|

　　...0
　　...1

　　 y shl 1
　　( x shl 1 )or 1

3:....__
___| .. |
___|__|
____._|
　　
　　...1
　　...0

　　 (y shl 1)or 1
　　 x shl 1