hdu 4686 Arc of Dream

<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=4686">點選打開hdu 4686</a>

思路: 矩陣快速幂

分析:

1 題目給定一個式子求和，那麼根據題目給定的，我們可以求出an*bn = (an-1*Ax+Ay)*(bn-1*Bx+By) =&gt; an-1*bn-1*Ax*Bx+an-1*Ax*By+bn-1*Ay*Bx+Ay*By

2 那麼我們根據上面的等式可以推出矩陣的乘法

3 那麼我們要求的是AoD(n)相當于求左邊矩陣的n次幂，然後利用結果乘上初始值

4 注意特判n為0的時候，結果為0。然後注意初始的值

代碼: