作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 105清大演算法
時間Mon Feb 4 17:43:04 2019
https://i.imgur.com/qVSPzoF.jpg
https://i.imgur.com/koRA6OH.jpg
這題大概了解是怎麼切割的
不過有些地方一直卡住
想問的是
花O(n)merge成的u1v2+u2v1是最後的uv相乘的結果嗎
還是(u1+u2)(v1+v2)這個才是
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.224.19
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549273386.A.B01.html
※ 編輯: AAQ8 (27.246.224.19), 02/04/2019 17:43:44
1F：推 TEPLUN: 從中間切 之所以可以直接算u1v2+u2v1是因為權重相同可以加 02/04 17:46
2F：→ TEPLUN: 起來再位移 02/04 17:46
3F：→ AAQ8: 那最後應該是要把u1v1,u2v2,u1v2+u2v1這三個merge起來才是uv 02/04 18:39
4F：→ AAQ8: 相乘的結果吧 02/04 18:39
5F：→ AAQ8: 還是我哪裡想錯了QQ 02/04 18:40
6F：→ DLHZ: 假設u=u1×10^n+u2, v=v1×10^n+v2, uv即u1×v1×10^2n+(u1+ 02/04 20:15
7F：→ DLHZ: u2)(v1+v2)×10^n+u2×v2 這東西其實叫Karatsuba 02/04 20:15
8F：→ DLHZ: 正確性其實大概證一下就知道了 其他有興趣可以去google看看 02/04 20:16