https://i.imgur.com/qVSPzoF.jpg
https://i.imgur.com/koRA6OH.jpg
這題大概了解是怎麼切割的
不過有些地方一直卡住
想問的是
花O(n)merge成的u1v2+u2v1是最後的uv相乘的結果嗎
還是(u1+u2)(v1+v2)這個才是

從中間切 之所以可以直接算u1v2+u2v1是因為權重相同可以加起來再位移

那最後應該是要把u1v1,u2v2,u1v2+u2v1這三個merge起來才是uv相乘的結果吧還是我哪裡想錯了QQ

假設u=u1×10^n+u2, v=v1×10^n+v2, uv即u1×v1×10^2n+(u1+u2)(v1+v2)×10^n+u2×v2 這東西其實叫Karatsuba正確性其實大概證一下就知道了 其他有興趣可以去google看看