作者j12345453 (CJentalL)
看板Grad-ProbAsk
标题演算法 Divide and conquer
时间Sat Dec 11 13:20:03 2021
https://i.imgur.com/cAHPDBO.jpg
如题
清大这题把Bit切分成前後半
又特别讲解要做出u1v2+u2v1
原因是什麽呀
这样跟u1v1直接乘有什麽差别呢
----
Sent from
BePTT on my iPhone 11
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.72.97.138 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1639200005.A.6A1.html
2F：→ VF84: 你参考看看 12/11 14:03
3F：推 VF84: TL;DR: 因为 u1v2 和 u2v1 的位移都是 n/2，所以并在一起算 12/11 14:16
4F：→ j12345453: 请问为何前半段的u1 v1反而不成上权重呢 12/11 14:42
5F：→ j12345453: 後半段的数比较小反而乘上权重 12/11 14:42
6F：推 VF84: 因为 u1v1 不用位移呀 12/11 14:44
8F：→ VF84: 阿，我好像知道我哪里弄混你了 12/11 14:50
9F：→ VF84: 我的算式里 u2 和 v2 是比较高的位元 12/11 14:50
10F：→ VF84: 跟题目反过来 12/11 14:51
11F：→ j12345453: 阿我懂了 谢谢大大讲解 12/11 14:55
12F：→ j12345453: 你是把U2 V2当作前半段对吧 12/11 14:55
13F：推 VF84: 嘿嘿没错 12/11 14:56
14F：→ j12345453: 那我另外想请问 12/11 14:57
15F：→ j12345453: 我贴文的图片里 12/11 14:57
16F：→ j12345453: 最後Merge阶段是thetaN 12/11 14:57
17F：→ j12345453: 那是因为各but相加吗 12/11 14:57
18F：推 VF84: 可以这样说。在利用递回算出那三组算式後，剩下的就只剩加 12/11 14:59
19F：→ VF84: 减法跟位元位移的运算了，这些可以在 theta(N) 内算出 12/11 14:59
20F：→ j12345453: Bit 12/11 15:02
21F：→ j12345453: 不过感觉这题最Tricky的地方是在 12/11 15:05
22F：→ j12345453: 我怎麽想的到u1v2+u2v1 可以用(u1+u2 )(v1+v2)乘出来 12/11 15:05
23F：→ j12345453: 虽然这不是很难 12/11 15:05
24F：→ j12345453: 但一开始真的想不到可以这样 12/11 15:05
25F：推 VF84: 我 conquer 这题的思考过程，是先用最原始的方法算，然後看 12/11 15:07
26F：→ VF84: 哪里是可以化简的。 12/11 15:07
27F：→ VF84: 再来就是靠想像力了 12/11 15:08
28F：推 VF84: 分解再重组，钢之链金术师都有教 12/11 15:10
29F：推 NCTUCKCurry: 我的想法是u1v2和u2v1的位移量是一样的 所以可以直接 12/11 16:25
30F：→ NCTUCKCurry: 算他们的和 12/11 16:25
31F：推 joywilliamjo: karatsuba变形吧，当场没看过真的很难想到 12/11 20:35