※ 引述《tkcn (小安)》之銘言：
: 再補充一下好了，
: 步驟 (1) 矩陣相乘時，被乘數和乘數都是同一個矩陣
: 其實只需要用到 7 次乘法。
確實如 jlovet 所說，
f(n-1) f(n)
f(n) f(n+1)
此種型式的矩陣相乘(平方)，
只需要 4 次乘法與 3 次加法
因此 f(10000) 使用 bottom-up，
乘法次數為: 13*4 + 4*4 = 68
加法次數為: 13*3 + 4*2 = 47
呼，這樣應該有幫 Q-matrix 平反了吧
--
有時候真的覺得大學時沒參加到 ICPC 還蠻可惜的...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.183.196
→
11/04 17:45, , 1F
11/04 17:45, 1F
推
11/04 18:35, , 2F
11/04 18:35, 2F
→
11/04 18:38, , 3F
11/04 18:38, 3F
→
11/05 10:56, , 4F
11/05 10:56, 4F
→
11/05 10:58, , 5F
11/05 10:58, 5F
→
11/05 11:27, , 6F
11/05 11:27, 6F
→
11/05 11:29, , 7F
11/05 11:29, 7F
討論串 (同標題文章)