POJ 3233 Matrix Power Series(矩陣優化)
題意:求S[k] = A + A^2 + ..... + A^k
利用矩陣快速冪可以很快的求出A矩陣的k次方, 但是該題是求和, 如果還按照原來的方法, 將要計算k次, 復雜度無法承受。
我們可以構造一個矩陣 (A 0)
(E E)
此時令S[k] = E + A + A^2 + ..... + A^(k-1)
那麼 ( A^k ) ( A 0)(A^(k-1)) (A 0 )^k (E)
= =
(S[k] ) (E E)(S[k-1] ) (E E ) (0)
那麼, 我們只要計算出S[k+1] = E + A + .... + A^k
然後將對角線元素-1就行了。
細節參見代碼:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include