69 条题解

  • 0
    @ 2008-10-21 14:21:29

    编译通过...

    ├ 测试数据 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-20 22:17:41

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    DIV 二分

  • 0
    @ 2008-10-18 21:23:31

    没有用矩阵乘法的同志们注意

    k mod m=0 时 不用再处理了

  • 0
    @ 2008-10-16 10:53:44

    建议倍增,找环如果数据强点会挂的.

    也就是说环很大的时候.

    倍增舒服..不过我居然把longint 打成int...

  • 0
    @ 2008-08-26 20:16:38

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    高中生。

    刚看过《密码传奇》,波兰人破译Enigma时就用了群论方程……,我只知道一个“字母循环圈”,然后本题就用类似的方法了。

    效果还不错,56ms

  • 0
    @ 2008-08-22 13:03:51

    ……矩阵乘法不懂

    先把m*10000以内的转换算出来

    然后k就可以处理了,速度不慢

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-07-25 21:53:52

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    好囧的矩阵乘法..快速幂+矩阵乘法??囧..

  • 0
    @ 2007-11-16 21:26:42

    矩阵乘法+快速幂运算

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2007-11-10 10:40:58

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    好不容易把题看明白了。。。

    然后好不容易把样例过了。。。。

    然后就简单得1遍ac了。。。

  • 0
    @ 2007-11-06 20:23:35

    呵呵,先求出群中操作m次后的摆放方法,再利用快速幂加速,细心点就可以,很快的。不信看下面。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2007-10-11 19:52:49

    拟快速乘方

  • 0
    @ 2007-10-10 16:24:58

    我是第100个过的.纪念一下.呵呵

    这道题是经典的矩阵乘法的题目,很简单.

  • 0
    @ 2007-08-17 15:38:39

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2007-07-25 23:37:54

    mick牛弄的慢了。。

    其实可以直接二分的

    把那个k先div m

    然后就是它转过了多少圈。把这个圈数二分的化复杂度小的多

    大概是。。。O(n*log[k/m])。似乎比O(m*n^2)快了很多。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    对了。。第100题纪念。。。

    开始时太低估那个k了。。。以为把它看作一圈圈的话就很快了。。。结果。。。

    没想到,睁大眼睛一看:那个k那么大。。。

  • 0
    @ 2007-07-01 15:24:30

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    题目输入的a意思是对于第i步操作,我们是把序列的第a位放到第j位去,(废话哦~~)

    我们把他转换1下,改为a意思是第i步操作,是把序列的第j位放到a位去..

    例如:

    题目样例---|>>>>(改变为)

    2 6 3 7 5 1 4

    7 2 1 3 4 5 6

    2 6 3 4 5 7 1

    5 6 4 7 1 2 3

    6 1 3 4 7 5 2

    对于第i个数t,就可以

    t:=i;

    for j:=1 to k do t:=a[(j-1) mod m+1,t];

    显然时间是O(nk);

    但是我们不难发现,经过不大于N*M步,t会回到同1个位置的..

    拿样例来说.对于第1个数,t的变化应该是

    1-2-2-6-2-1-2-2-6-2-1-....1-2-2-6-2循环

    第2个数:

    2-6-5-5-1-6-1-7-1-5-7-4-3-3-4-4-7-6-6-3-3-3-1-2-6-5-5-4-4-7-2-

    6-5-5-1-6-1-7-1-5-7-4-3-3-4-4-7-6-6-3-3-3-1-2-6-5-5-4-4-7-2..

    2-6-5-5-1-6-1-7-1-5-7-4-3-3-4-4-7-6-6-3-3-3-1-2-6-5-5-4-4-7循环

    而且循环长度是m的倍数,就是说当循环x个回合,t=i是,序列重复!!

    所以我们只需要求出循环的长度l(=x*m).然后ki:=(k-1) mod l+1;

    t:=i;

    for j:=1 to ki do t:=a[(j-1) mod m+1,t];

    那么时间复杂度就只有O(Nl)

  • 0
    @ 2007-06-05 16:32:36

    有更详细的题解吗

  • 0
    @ 2007-05-27 19:50:32

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行时错误...| 错误号: 216 | 存取非法

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

    Unaccepted 有效得分:40 有效耗时:0ms

  • 0
    @ 2007-03-24 21:02:59

    编译通过...

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

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

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

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

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

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

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

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

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

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

    这题不难啊……

    可以吧两个操作用O(n)时间合并为一个,再二分即可……

    用不着那么复杂的东西……

  • 0
    @ 2007-03-24 13:34:06

    记住分治时用int64 我为此郁闷了N久

  • 0
    @ 2006-11-14 20:48:41

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    找出某一位经过K*M次回到原先的最小K值。将所有位的K值求最小公倍数在乘以M,得到整个序列的循环。

信息

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