之前 TLE,一直沒去理他,心血來潮複習一遍。

Matrix Gk[i][j] 表示 i->j 走 k 步的方法數。

有 Gk = G(i+j) = Gi * Gj,得 Gk = (G1)^k,快速冪(O(n^3lgk))。

再加上這題詢問很多次,所以可以先把 2^i 的 Matrix 先建好。

我的code

http://codepad.org/EXF2n9vO

p.s: 有個小地方就是 當 k=0 && u==v 時 答案是 1(Matrix裡是0)。

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()