#29663:


becaido (Caido)

School : 臺北市立建國高級中學
ID : 83294
IP address : [60.248.156.9]
Last Login :
2024-11-13 00:08:35
f996. N項的費氏數列 - Extreme -- Caido | From: [140.112.102.5] | Post Date : 2022-03-19 12:19

首先這題要用矩陣快速冪,矩陣快速冪裡會有的東西是 $\color{black}{ans = ans\times mat}\ $ 和 $\color{black}{mat = mat\times mat}\ $,其中 $\color{black}{ans}\ $ 為欲求的矩陣,$\color{black}{mat}\ $ 則是一個 $\color{black}{2^i}\ $ 次的矩陣,如果直接運算,複雜度會是 $\color{black}{O(t\times n^3log(k))}\ $,套在這一題會 $\color{black}{\text{TLE}}\ $。

$\color{black}{mat}\ $ 其實在每次運算的時候值都是固定的,所以我們其實可以預處理好,就不用每次都乘一遍。那要如何改善 $\color{black}{ans = ans\times mat}\ $ 呢?可以發現 $\color{black}{ans}\ $ 不一定要是一個 $\color{black}{n\times n}\ $ 的矩陣,可以是一個 $\color{black}{1\times n}\ $ 的矩陣,這樣乘法就從 $\color{black}{n^3}\ $ 變成 $\color{black}{n^2}\ $ 了。於是預處理的複雜度加上快速冪的複雜度,最終就是 $\color{black}{O(n^4log(C)+t\times n^2log(k))}\ $。

 
ZeroJudge Forum