發表新討論
#25538: 矩陣乘法 + 快速冪


allllllan123456 (God of Computer Science)

學校 : 國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
d769. 共有多少種走法? -- 國文課時的靈機一動(誤 | From: [125.231.121.9] | 發表日期 : 2021-05-30 21:39

這題 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
d769. 共有多少種走法? -- 國文課時的靈機一動(誤 | From: [125.231.133.241] | 發表日期 : 2021-07-04 18:25

這題 AC 率高，應該是因為解法蠻經典的，用一個矩陣 M1 表示任兩點間走 k1 步的方法數，用另一個矩陣 M2 表示任兩點間走 k2 步的方法數，那麼 M1 * M2 代表任兩點間走 k1+k2 步的方法數。那把 k 用二進位表示之後就可以用快速冪得到最後的矩陣。


https://alan23273850.github.io/Online-Judge-Problems/zerojudge/d769/

 
ZeroJudge Forum