這題是矩陣乘法，但是直接乘一定會爆掉(n^3)，所以要利用矩陣乘法的結合率(矩陣沒有交換率，但有結合率)，先randen一個1*n的矩陣L，(A*L)*(B*L)=(C*L)，這樣的情況有兩種:
1.不一樣，錯了就錯了
2.對了，不一定對(因為這樣算法會出現剛好一樣得狀況)
這就延伸出雖機的算法了，隨機演算法有-Las Vegas algorithm 和 Monte Carlo algorithm等等，其中 Las Vegas是一種猜測答案會對的演算法，而Monte Carlo則是利用機率來提高自己答案的正確性，以這題來說，因為錯了就錯了，但是對了有1/2的機會還是錯的，所以就多randen幾個L，做五次錯的機率就變成 1/2^5=1/32，基本上就AC了，而且出測資的人又不知道你的randen是多少ㄏ....。
沒有留言:
張貼留言