作者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/cn.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