可以解释一下如何构造k叉树解这题么？#

Links:

http://www.matrix67.com/blog/?s=%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95

http://www.research.att.com/~njas/sequences/A000045

http://www.research.att.com/~njas/sequences/A000073

http://www.research.att.com/~njas/sequences/A000078

http://www.research.att.com/~njas/sequences/A001591

http://mathworld.wolfram.com/Fibonaccin-StepNumber.html

矩阵*

type

mat=array[1..10,1..10] of qword;

var

x,y:mat;

k,n,i,j:longint;

a:array[0..10] of qword;

p:qword;

procedure cf(var a,b:mat);

var

c:mat;

i,j,l:longint;

begin

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

for i:=1 to k do

for j:=1 to k do

for l:=1 to k do

begin

inc(c,(a mod 7777777)*(b[l,j] mod 7777777));

c:=c mod 7777777;

end;

a:=c;

end;

begin

readln(k,n);

for i:=1 to k-1 do x:=1;

for i:=1 to k do x[k,i]:=1;

a[1]:=1;a[2]:=1;for i:=3 to k do a[i]:=a*2;

if n and 1=1 then y:=x else begin for i:=1 to k do y:=1;end;

n := n shr 1;

while n>0 do

begin

cf(x,x);

if n and 1=1 then cf(y,x);

n := n shr 1;

end;

for i:=1 to k do

begin

inc(p,y[1,i]*a[i]);

p:=p mod 7777777;

end;

writeln(p);

end.

唉，矩阵横竖写反了，交了2次才检查出来，真WA。

矩阵A=a*b

矩阵B=b*c

矩阵c=a*c

矩阵A*矩阵B，运算法则为：

for (i=1;i

强大的矩阵。

快速幂写错。。。。调了好久

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

关键在构造这个矩阵

０。。。。１

１。。。。１

０１。。。１

。。。。。。

。。。。。。

０。。。１１

思路近似于斐波那契，但会超，到最后房间也难以实现，所以用矩阵做。

Warcraft III 永远支持！

dotA 是好地图！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢日文大牛和邵琦大牛....

我用我自己都不知道的矩阵乘法过了

还是不懂

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我也喜欢矩阵,哈哈!

构造k叉树，最后统计叶子节点的个数就OK了~~~可惜空间会爆掉

..利用矩阵乘法的结合律

转换矩阵(c): 答案用矩阵(ans):

0 1 0 0 0 0 0..... f[1]

0 0 1 0 0 0 0..... f[2]

0 0 0 1 0 0 0 .... f[3]

0 0 0 0 1 0 0 ... f[4]

0 0 0 0 0 1 0 ... f[5]

..... ...

1 1 1 1 1 1 1.....(k*k) f[k]

算出 c^(n-k)*ans (用快速幂) 输出答案就是f[k]

注意.运算过程中不停.MOD....还有一定要用qword或者int64....

一次ac..

我太爱矩阵了。

核心代码

function dose(b:arr;n:longint):arr;

var

tem:arr;

begin

if n=1 then exit(b);

tem:=dose(b,n shr 1);

tem:=mult(tem,tem,k,k,k);

if n and 1=1 then

tem:=mult(b,tem,k,k,k);

exit(tem);

end;

太经典的二分快速幂。

矩阵太神奇了^^

777777也是个好数

777777*777777 < maxint64

777777*777777*10 > maxint64

第一次

t+=(x[a][i][k]*x[k][j])%7777777;

结果wa了

改为

t=(t+x[a][i][k]*x[k][j])%7777777;

就ac了~

Magic Matrix ！

AC一题真是不容易。。

一定要用int64!!

不做这道题，还不知道矩阵有如此神奇的用处。