69 条题解

  • 0
    @ 2009-09-27 13:53:40

    矩阵连乘。每次置换都可以看做乘一个矩阵。如操作 3 1 2 4,

    相当于

    0 0 1 0 1

    1 0 0 0 2

    0 1 0 0 乘以 3

    0 0 0 1 4

    将m操作合并,即按操作顺序连乘,再求最后合并矩阵的(k/m)次方,最后k%m就一一相乘模拟就OK了~

  • 0
    @ 2009-08-27 16:47:26

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    本来想用这题来练习刚学的矩阵的~~

    可是做了才发现根本不用矩阵……

    把m次合成一次 做k div m 次(二分快速幂优化)

    再最后做k mod m 前个

  • 0
    @ 2009-08-23 13:17:57

    二分快速幂卡了我好久,矩阵放到递归里面返回把栈给爆了,只好先递归分解幂,然后逐个判断分解的出来数的奇偶,再乘。

    最后两点有点慢,懒得位运算了。

    编译通过...

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-08-21 22:29:35

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    压缩压缩狂压缩……

    虽然没秒杀。。。。

  • 0
    @ 2009-08-13 14:40:45

    强悍的题...交了7次......

    我是个菜油....

    有些感想:

    1.可以不用矩阵

    2.一定用2分

    3.可以找循环节

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

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-08-05 20:26:29

    我弱 矩阵乘法哪个在左边哪个在右边没想清楚。。。糊涂凑对样例。。。糊涂AC。。我若 置换那里没想清楚....

  • 0
    @ 2009-08-01 15:30:48

    压缩压缩再压缩……直到压缩不下去为止!

  • 0
    @ 2009-07-30 19:14:03

    大牛们说的太精炼了,我研究了半天

    其实只要先做x次,这个x可以设到n*10000

    然后记下来做这些次数的结果,后面先做k div x,这时的操作就是记下来的n*10000次的更新结果

    再做k mod x 次,按原来的做

    不过这样貌似不能0ms

    有错的话,请大牛指教

  • 0
    @ 2009-07-19 14:46:59

    其实直接小倍增就可以0ms

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var aa,ex,tmp,b:array[0..100]of longint;

    a:array[0..10,0..100]of longint;

    k:int64;

    j,circle,n,m,i,tot:longint;

    flag:boolean;

    procedure make(p:longint);

    var i:longint;

    begin

    tmp:=b;

    for i:=1 to m do

    b[i]:=tmp[a[p,i]];

    end;

    begin

    readln(m,n,k);

    for i:=0 to n-1 do

    for j:=1 to m do read(a);

    for i:=1 to m do b[i]:=i;

    i:=n-1;ex:=b;tot:=0;flag:=false;

    while k>0 do

    begin

    dec(k);

    tot:=tot+1;

    i:=(i+1)mod n;

    make(i);

    if tot=10000*n then begin flag:=true;aa:=b;break;end;

    end;

    if flag then begin

    while K>10000*n do

    begin

    k:=k-10000*n;

    tmp:=b;

    for j:=1 to m do b[j]:=tmp[aa[j]];

    end;

    i:=n-1;

    while k>0 do

    begin

    dec(k);

    i:=(i+1)mod n;

    make(i);

    end;

    end;

    for i:=1 to m-1 do write(b[i],' ');

    writeLn(b[m]);

    end.

  • 0
    @ 2009-05-29 10:07:34

    矩阵乘法,不懂看这里吧:

    http://www.matrix67.com/blog/archives/276

  • 0
    @ 2009-05-27 01:00:33

    编译通过...

  • 0
    @ 2009-05-12 23:54:25

    全部0ms.

    注意到如果对于这m行如果执行的次数足够多,就会回到“1,2,3,...,n”.

    本着这条性质,有如下的方案:

    ①求出执行完m行后的状态,组成置换(1,2,...,n)--(f1,f2,...,fn)(*)

    ②求出上述置换()的循环周期 T

    ③x:=(k div m) mod T

    ④从(1,2,...,n)的状态出发将置换(
    )执行x次,得到(k1,k2,...,kn)状态

    ⑤对于(k1,k2,...,kn)执行矩阵的前(k mod m)行,得到新状态(ans1,ans2,...ansn)

    ⑥输出上述得到的状态

  • 0
    @ 2009-04-22 16:16:51

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

    快速幂好像慢了点…………

    一开始递归忘了回带矩阵的值,0分~~55555555

  • 0
    @ 2009-03-26 23:19:12

    这道题目是我第一道自己想出来的矩阵乘法题目,其实不是很难

    我是用n*n的0,1矩阵表示状态

    把每次修改看成是一次矩阵乘法,然后就是快速幂

  • 0
    @ 2009-01-11 00:15:00

    拥有矩阵的性质所以有结合率

    当然不需要矩阵操作即可完成了

    struct F

    {

    int x[101];

    F operator *(F u)

    {

    F t;

    for(int i=1;i

  • 0
    @ 2008-11-13 19:33:27

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    第一次做时脑子进水了,居然以为O(k/m)的能过。。40

    痛定思痛,上快速幂! AC~

    P.S.矩阵乘法怎么做?。。

  • 0
    @ 2008-11-11 09:01:38

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

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

    我怎么觉得矩阵是LOG(K/M)*N^3的??没弄清..

    反正置换的结合有结合律,直接二分最快

  • 0
    @ 2008-11-07 09:36:44

    郁闷中间PASCAL卡死

    在万分悲痛中,重写,

    又把N的范围看成10...

    INT64开成了LONGINT...

    终于过了...

  • 0
    @ 2008-11-06 11:18:59

    先把m个操作压缩成一个。再进行加速迭代,(应该就是大家所谓的“倍增”吧。本人一直称之为加速迭代。)此题中运用加速迭代的本质也是压缩。

    时间复杂度O(ln(k)/ln(2)),相当好做。

  • 0
    @ 2008-10-27 20:18:36

    矩阵真好用!!!

信息

ID
1049
难度
5
分类
组合数学 点击显示
标签
递交数
1452
已通过
494
通过率
34%
被复制
12
上传者