> 易知[p(i) p(i+1)] * [0  q] = [p(i+1) p(i+2)]
>                     [1  p]
> 每个bomb之间为一段，可以算出在bomb之前一格的概率。再*q就是bomb之后一格的概率了。

我是把每個bomb 例如bomb在2, 20

則p(21) = p(3) * p(3 to 19) * q

p(3 to 19)我把他分成兩部分

拆成 (1) p(3 to (3 + 19)/2) 和 p((3 + 19)/2 + 1 to 19)
加上 (2) p(3 to (3 + 19)/2 - 1) 和 p((3 + 19)/2 + 2 to 19) 乘上 q 

(1) : 3-----------11   12-----------22
         p(3 - 11)       p(12 - 22)

(2) : 3----------10 11--12 13----------22
         p(3 - 10)     q     p(13 - 22)

利用P(n + 1) = P(n)(p - 1) + 1 ， 
可以利用 p(3 - 11) 求出  p(3 - 10) 
以及利用 p(12 - 22) 求出 p(13 - 22)

並且將算出的值存入map中，化簡成O(N * log(100000000))

不知道有沒有人試過這樣AC = = 我還在WA

• Re: 快速求幂。 (0) MasterLuo 2009-08-23 17:55:32