題目連結：
題目大意：
輸入給定一個非負整數 t （t < 2 ^ 64）以及兩個機率值 a 、 b（0 ≦ a 、 b ≦ 1），代表當前狀態如果是交易成功之狀態，則下一秒有機率 a 會變為交易失敗；反之，如果目前是交易失敗的狀態，則有機率 b 會變為成功。
已知一開始（t = 0）時，狀態為交易成功。試問 t 秒後，交易成功的機率為何？請四捨五入至小數點第二位後輸出。
範例輸入：
範例輸入 #1
1 0.55 0.45
範例輸入 #2
1000000000 0.12 0.79
範例輸入 #3
25830031103833600 0.29 0.49
範例輸出：
範例輸出 #1
0.45
範例輸出 #2
0.87
範例輸出 #3
0.63
解題思維：
因為一開始的狀態為交易成功。所以我們可以將成功 & 失敗的機率分布寫成一個 2 × 1 陣列 D =
1
0
接著使用如下 2 × 2 的轉移矩陣（Transition Matrix） P =
1 - a b
a 1 - b
其四個位置由上往下、由左至右的意涵為「成功變為成功」（即不變）、「失敗變成成功」、「成功變成失敗」以及「失敗變成失敗」這四個機率。
根據轉移矩陣的特性，我們可以得到第 t 秒的成功與失敗機率分布為
D' = P ^ t × D
（注意這個結果跟 D 的維度是一樣的，即 2 × 1）
而所求是問成功的機率，因此為 D' 的兩個元素中在上面的那一個元素。又因為一開始的 D 只有上面那一項為 1 ，所以所求恰好為 p ^ t 這個矩陣左上角的那個元素值。
至於 p ^ t 的求法則需要快速冪來加速（原理可以參見這題中間的說明），不然直接計算會因為 t 值太大而超時。
最後，要注意浮點數誤差會因為矩陣的次方值越大而累積得越大。所以當前一次迭代的轉移矩陣裡面元素的值與這一次的相差不遠（差值小於 10 ^ (-5) 等等）就視為這次的計算等同於誤差，因此不更動前一次的矩陣內容。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
