97 条题解

  • 0
    @ 2009-03-18 16:06:19

    矩阵*

  • 0
    @ 2008-12-27 13:21:10

    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.

  • 0
    @ 2008-12-26 16:24:00

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

  • 0
    @ 2008-11-23 16:05:41

    矩阵A=a*b

    矩阵B=b*c

    矩阵c=a*c

    矩阵A*矩阵B,运算法则为:

    for (i=1;i

  • 0
    @ 2008-11-07 08:21:03

    强大的矩阵。

  • 0
    @ 2008-11-05 12:13:11

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

  • 0
    @ 2008-11-01 14:25:20

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    关键在构造这个矩阵

    0。。。。1

    1。。。。1

    01。。。1

    。。。。。。

    。。。。。。

    0。。。11

  • 0
    @ 2008-10-28 20:50:35

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

    Warcraft III 永远支持!

    dotA 是好地图!

  • 0
    @ 2008-10-27 12:22:20

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-17 22:31:08

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

    还是不懂

  • 0
    @ 2008-09-26 22:06:35

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    我也喜欢矩阵,哈哈!

  • 0
    @ 2008-09-26 20:57:43

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

  • 0
    @ 2008-09-13 07:53:08

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

    转换矩阵(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....

  • 0
    @ 2008-09-29 17:24:39

    一次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;

    太经典的二分快速幂。

  • 0
    @ 2008-08-26 12:13:36

    矩阵太神奇了^^

    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了~

  • 0
    @ 2008-07-25 18:09:40

    Magic Matrix !

  • 0
    @ 2008-07-15 10:22:44

    AC一题真是不容易。。

  • 0
    @ 2007-11-14 08:01:12

    一定要用int64!!

  • 0
    @ 2007-11-09 15:08:55

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

信息

ID
1067
难度
6
分类
动态规划 | 线性代数 | 矩阵乘法 点击显示
标签
(无)
递交数
3080
已通过
826
通过率
27%
被复制
16
上传者