關於更快的計算遞推式的問題？

02-18

今天做了一個dp 題，推出了狀態轉移方程，然後可以用矩陣快速冪遞推，由於複雜度還是太高(m^3logn的複雜度，m最大200，n最大1e18)，所以想繼續優化，《挑戰程序設計》上關於遞推式的優化有提到，但是沒有具體的說明，百度了一下也沒有搜到。還請大神賜教。

線性遞推關係與矩陣乘法

這個裡面有個優化，不過我還沒太看懂，看懂了來更新。

----------------------

見評論

先求出矩陣的特徵多項式，然後利用多項式逆元來做多項式求Mod。整個過程當然離不開FFT，有精度問題的話還要用NTT，模數比較大，且不是a*2^k + 1型的質數時，可能要跑多遍配合crt，可以優化到m*logm*logn。很快吧？其實並不，用crt的話，m只敢算1w以下。

——————————————————————————————————

補充一下，大家去看 @ftiasch 的那篇論文吧，樓上都給了連接，當年也是沒看懂，然後X姐QQ上教的我。然後這兩年被OIer引入黑科技，從m^2*logn優化到了m*logm*logn。論文中的線性表示部分，可以用多項式乘法來做，逆向部分可以用多項式求Mod來做，大概就是這樣吧。

矩陣乘法遞推的優化

k階常係數齊次線性遞推O(k^2logn)演算法

i可以有klogklogn的做法

具體見叉姐論文

http://wapwenku.baidu.com/view/bac23be1c8d376eeafaa3111.html?ssid=0from=844buid=0pu=usm@0,sz@1320_2001,ta@iphone_1_8.4_3_600bd_page_type=1baiduid=230041D826DC07AF67BE17E7835CB4EDtj=wenku_1_0_10_title#page/1/1441077134895

然而這還不是完全體…

你還得會fft搞多項式的除法和多項式取余

這部分可以在網上搜一下會有的