多谢curimit大牛提供的递推式Orz

终于过了..

我好笨啊55555~

首先我的矩阵乘法写成了for i := 1 to t ...

检查了十几分钟，将1改成了0。

然后又有莫名其妙的错误。。。

又检查了十几分钟，发现type tmatrix = array[1..31,1..31] of longint ;

这个在程序第一行的错误真隐蔽……

555555~

终于AC了。

楼下的的大牛谁的太复杂了我来说个简单的理解方法：

把m列的 XXXXX五位二进制转化成十进制（状态压缩）

不会矩阵乘法的自己去Google吧！

一个矩阵连乘n此后就表示每两个点间的长度为n的路径数量（不知为是么？）

初始矩阵可以用位运算，找规律，BFS求出

因为n很大所以要用快速幂运算，方法与一般情况整数相乘类似

大家看递推式：

当m=1时 f(n)=0 n为奇数

f(n)=1 n为偶数

当m=2时， f(n)=f(n-1)+f(n-2)

初值：f(1)=1 f(2)=2

当m=3时，f(n)=4f(n-2)-f(n-4

初值：f(1)=0 f(2)=3 f(3)=0 f(4)=11

当m=4时，f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)

　　 初值：f(1)=1 f(2)=5 f(3)=11 f(4)=36

当m=5时，f(n)=15f(n-2)-32f(n-4)+15f(n-6)-f(n-8)

初值：f(1)=0 f(2)=8 f(3)=0 f(4)=95 f(5)=0 f(6)=1183 f(7)=0 f(8)=14824

不会做难度是1的。。。伤自尊了。

不会做

拿来主义(那个矩阵乘法)

强大的矩阵乘法

program p1194;

const

try : array[1..7]of longint=(3,6,12,15,24,27,30);

type

sqtype=array[0..31,0..31]of longint;

var

base,temp,lim,i,j,k,n,m : longint;

ans,w : sqtype;

flag : boolean;

procedure mult(a,b : sqtype; var c : sqtype);

var

i,j,k : longint;

begin

fillchar(c,sizeof(c),0);

for i := 0 to lim do

for j := 0 to lim do

for k := 0 to lim do

c := (c+(a*b[k,j]) mod base) mod base;

end;

procedure calc(x : longint);

begin

if x=1 then exit;

calc(x shr 1);

mult(ans,ans,ans);

if odd(x) then mult(ans,w,ans);

end;

begin

readln(n,m,base);

lim := 1 shl m -1;

for i := 0 to lim do

begin

temp := (not i) and lim;

w := 1;

for j := 1 to 7 do

if try[j]>lim then break

else

begin

flag := true;

for k := 0 to (m-1) do

if ((try[j] shr k) and 1=1)and((temp shr k) and 1=1) then

begin

flag := false;

break;

end;

if flag then

w[i,temp or try[j]] := 1;

end;

end;

ans := w;

calc(n);

writeln(ans[lim,lim]);

end.

3进制也行，就是速度慢些

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 88ms

├ 测试数据 12：答案正确... 134ms

├ 测试数据 13：答案正确... 9ms

├ 测试数据 14：答案正确... 41ms

├ 测试数据 15：答案正确... 9ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 9ms

├ 测试数据 19：答案正确... 9ms

├ 测试数据 20：答案正确... 9ms

├ 测试数据 21：答案正确... 25ms

├ 测试数据 22：答案正确... 88ms

├ 测试数据 23：答案正确... 0ms

├ 测试数据 24：答案正确... 56ms

├ 测试数据 25：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：593ms

不能说是DP，应该说是递推吧，没有所谓“最优”的摆放。

用矩阵+快速幂优化，自己测11个点只用0.17S

程序只有48行，我觉得这个题目极经典，所以把自己的代码贴上来供参考

其实理解了矩阵乘法的图论意义后思路就会显得“十分显然”。

矩阵G自乘N次后得到的矩阵G`的意义是，G`表示从i到j走N步到达的路有多少条。

这题就变成了从状态“11111”（假设存在状态N=0，计算的时候不用考虑）到状态“11111”（M=5）的长度为N的路有几条，原来的矩阵G可以预处理出来。

进制的转化就不讲了。

用I表示前一个状态，J表示这个状态，则I可以到达J的条件是：（K = 2^M - 1 ）

I OR J = K 且 I AND J = AG[W]

AG[W]是一个常数数组，自己手算算出来的

const ag:Array[0..7]of longint = (0,3,6,12,15,24,27,30);

大家把里面的数字转换成2进制就知道这个数组的干吗用的了。

简单地说，就是I状态和J状态在某个位置必须至少有一个是1，如果I是1，J是0，那么就说明这个地方不用放骨牌，如果I是0，J是1那么就是放骨牌。如果I和J都是1，那么说明原来这个地方有骨牌了，现在还有，那么一定是横着放的骨牌，此时数组AG的作用就显现出来了，判断是不是满足连续的I，J都是1。

下面是程序：

type Matrix=Array[0..32,0..32]of longint;

const ag:Array[0..7]of longint = (0,3,6,12,15,24,27,30);

var i,j,k,m,n,l,r,p:longint;

ee,a,b,c:Matrix;

function mul(a,b:Matrix):Matrix; //矩阵乘法，这里不用看

var tmp:Matrix;

i,j,w,s:longint;

begin

for i:=0 to k-1 do

for j:=0 to k-1 do begin

s:=0;

for w:=0 to k-1 do begin

inc(s,a*b[w,j]);

if s>=p then s:=s mod p;

end;

tmp:=s;

end;

mul:=tmp;

end;

function pow(ma:Matrix;x:longint):Matrix; //快速幂，不会的可以看一下

var y:Matrix;

begin

if x and 1 = 1 then y:=ma else y:=a;

repeat

x:=x shr 1;

ma:=mul(ma,ma);

if x and 1 = 1 then y:=mul(y,ma);

until x

DP 方程是什么啊

我是按m的大小分类做的。

递推，用01表示当前状态，可以转化成十进制存。画个图就推出来了。

但是n很大，所以要加矩阵优化，用矩阵快速幂，转移矩阵自己构造吧。好复杂啊。。

囧死。。这题写了好久好久。。其实就是考快速幂，还出得这么复杂，程序好长好长。。。

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 0ms

├ 测试数据 23：答案正确... 0ms

├ 测试数据 24：答案正确... 0ms

├ 测试数据 25：答案正确... 0ms

110个 太高兴了 谢谢师傅 谢谢大家~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 0ms

├ 测试数据 23：答案正确... 0ms

├ 测试数据 24：答案正确... 0ms

├ 测试数据 25：答案正确... 0ms

我第100个,太幸运了!!!

请问高手，怎样用矩阵乘，我只用纯dp，结果超时了。

总算有题可以一次通过了..

我喜欢一片红字的感觉

zly ....

这道题你AC起来也不容易啊...

因为骨牌是1*2，

所以f[i]只跟f,f有关；

f[1]:=...;f[2]:=...;

f[i]:=f+f*f[2];(不知道对不对-_-!);