vijos上的题解：
1.因为每个格子不是被覆盖就是没被覆盖，状态只有0 1两种，m<=5，所以可以将每一列的状态压缩，看作一个二进制数.
2.矩阵G表示从I状态到J状态的路径条数，自乘N次为长度为N的路径条数。
3.矩阵乘法可以用快速幂优化，时间复杂度为O(logN*(2^M)^3)可以接受
4.用I表示前一个状态，J表示这个状态，则I可以到达J的条件是：（K = 2^M - 1 ）
I OR J = K 且 I AND J = AG[W]
I状态未能填满的格子均由横向1*2的骨牌填充，此时J状态相应的位置也填充了骨牌，因此要满足I OR J = K，即I和J状态此时互补。
又在J状态下可以继续填充竖向2*1的骨牌，这些骨牌的位置可由I AND J得到，所以I AND J必须满足 I AND J = AG[W]
AG[W]为在宽度为M是竖向填充2*1的骨牌的所有方案。
ag:Array[0..7]of longint = (0,3,6,12,15,24,27,30);
把里面的数字转换成2进制就知道这个数组的干吗用的了。
5.再次感谢matrix67大牛，膜拜ing...
还有需要弄清的问题是把每个数字转换为2进制后，1表示此位置被覆盖，0表示未被覆盖。但为什么需要 i or j=1<<m -1 并且 i and j=这些奇怪的数字呢？
其实我们可以这样考虑，我们现在所在的这一行，假设是n行，要过度到n+1行，所以这一行上面的0必须被填上，这样n+1行的同一个位置必定有1，
这是横着铺了一个骨牌的结果，所以i or j=1<<m-1
那为什么要有i and j=那些呢？
我们思考，当把第n行铺满之后，在n+1行上竖着铺放骨牌还可以得到不同的方案数，而这时能铺的只有n行的1所在的位置，而且必须是若干个两个连着的1。
而 i and j 的1所在位置就是新铺的竖着的骨牌，它必须等于某些特定的值，而不能等于其它的值 比如 01010 这是显然不可能，他是怎么铺上的呢？
事实上，我们把AG数组的所有转化为二进制即：
00000,00011,00110,01100,01111,11000,11011,11110
这为我们提供了所有可行的i and j 的值
Q.E.D
代码：
const ag:array[..]of longint=(,,,,,,,);
type matrix=array[..,..] of longint;
var a,b:matrix;
i,j,k,m,n,p,ans:longint;
function mo(x:longint):longint;
begin
mo:=x mod p;
end;
procedure init;
begin
readln(n,m,p);
fillchar(a,sizeof(a),);
fillchar(b,sizeof(b),);
m:=(<<m)-;
for i:= to m do
for j:= to m do
if i or j=m then
for k:= to do
if i and j=ag[k] then a[i,j]:=;
for i:= to m do b[i,i]:=;
end;
procedure mul(var x,y,z:matrix);
var t:matrix;
i,j,k:longint;
begin
fillchar(t,sizeof(t),);
for i:= to m do
for j:= to m do
for k:= to m do
t[i,j]:=mo(t[i,j]+x[i,k]*y[k,j]);
z:=t;
end;
procedure ksm(cs:longint);
begin
while cs<> do
begin
if cs and = then mul(a,b,b);
cs:=cs>>;
mul(a,a,a);
end;
end;
procedure main;
begin
ksm(n);
writeln(b[m,m]);
end;
begin
init;
main;
end.
还有一个小问题，这里A数组自乘了n次，而且最后直接输出了b[m,m]，这是为什么呢？
我们可以假想初始状态为0行铺满了格子，每乘一次都得到了下一行的结果，所以n此后得到了第n行的结果，A[n,n]表示的就是从第0行铺满到第n行铺满的方案数。