#25538: 矩陣乘法 + 快速冪
allllllan123456
(God of Computer Science)
學校
:
國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
這題 AC 率高，應該是因為解法蠻經典的，用一個矩陣 M1 表示任兩點間走 k1 步的方法數，用另一個矩陣 M2 表示任兩點間走 k2 步的方法數，那麼 M1 * M2 代表任兩點間走 k1+k2 步的方法數。那把 k 用二進位表示之後就可以用快速冪得到最後的矩陣。
#25923: Re:矩陣乘法 + 快速冪
allllllan123456
(God of Computer Science)
學校
:
國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
這題 AC 率高，應該是因為解法蠻經典的，用一個矩陣 M1 表示任兩點間走 k1 步的方法數，用另一個矩陣 M2 表示任兩點間走 k2 步的方法數，那麼 M1 * M2 代表任兩點間走 k1+k2 步的方法數。那把 k 用二進位表示之後就可以用快速冪得到最後的矩陣。
https://alan23273850.github.io/Online-Judge-Problems/zerojudge/d769/