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

就是把k个命令看做一个转移矩阵，然后乘m次...转移矩阵可以在O(kn)的时间复杂度内构造出来

Posted by Ikki at 2009-05-17 18:39:52 on Problem 3735
In Reply To:请问你是怎么构造的呢 Posted by:gf_lu at 2009-05-17 18:08:51

Followed by:

我也是这么搞的，希望听听置换群的那个怎么搞。 (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