[理工] 105清大演算法

[AAQ8 ()]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1549273386.A.B01.html
※ 編輯: AAQ8 (27.246.224.19), 02/04/2019 17:43:44
推 TEPLUN: 從中間切 之所以可以直接算u1v2+u2v1是因為權重相同可以加
→ TEPLUN: 起來再位移
→ AAQ8: 那最後應該是要把u1v1,u2v2,u1v2+u2v1這三個merge起來才是uv
→ AAQ8: 相乘的結果吧
→ AAQ8: 還是我哪裡想錯了QQ
→ DLHZ: 假設u=u1×10^n+u2, v=v1×10^n+v2, uv即u1×v1×10^2n+(u1+
→ DLHZ: u2)(v1+v2)×10^n+u2×v2 這東西其實叫Karatsuba
→ DLHZ: 正確性其實大概證一下就知道了 其他有興趣可以去google看看