Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

是不是((bA+b)A+b)*A....+b这样的形式？

Posted by gf_lu at 2009-05-17 18:02:19 on Problem 3735
In Reply To:这个是不是矩阵乘法？ Posted by:Arithmetic at 2009-05-17 13:20:58

Followed by:

好象和我构造的不大一样 (0) majia5 2009-05-17 18:04:52
- 请问你是怎么构造的呢 (0) gf_lu 2009-05-17 18:08:51
  - 就是把k个命令看做一个转移矩阵，然后乘m次...转移矩阵可以在O(kn)的时间复杂度内构造出来 (0) Ikki 2009-05-17 18:39:52
    - 我也是这么搞的，希望听听置换群的那个怎么搞。 (0) ASCII 2009-05-17 18:41:25
      - 可是你的程序运行时间明显比我短很多哎，有什么特殊优化么？ (0) Ikki 2009-05-17 18:52:29
        Re:我构造的矩阵有一个特点。每一列只有一个元素算非0，所以乘法是n*n的，但是WA，能给个数据么？ (0) blackdog 2009-05-17 19:05:49
        用long long了没 (0) Ikki 2009-05-17 19:06:49
        Re:用了。比较直观的数据没啥问题。 (0) blackdog 2009-05-17 19:07:53
        二分求幂的过程中也一定满足？ (0) majia5 2009-05-17 19:55:24
        我做矩阵乘法的时候是先枚举一个矩阵a的第i行第j列，如果a[i][j]=0的话，下面的一层循环就可以不要了。 (0) ASCII 2009-05-17 19:23:44
        嗯……改成这样之后79ms了...@_@ (0) Ikki 2009-05-17 20:12:27
        这题考的就是优化了。。囧囧 (0) majia5 2009-05-17 20:16:57
        非常感谢！有了这个优化我的程序从TLE降到了60+msAC！ (3) IceKingdom 2009-05-21 16:24:50
    - 那操作g要怎么处理呢 (0) gf_lu 2009-05-17 22:20:54

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator