T4 时空の穿越：矩阵
题意简化
给定序列 FFF，有：
Fi={1,1≤(i≤5)Fi−1+2×Fi−2+3×Fi−3+5×Fi−4+8×Fi−5,(i≥6)\begin{equation*} F_i= \begin{cases} 1, & 1\le (i\le 5)\\ F_{i-1}+2\times F_{i-2}+3\times F_{i-3}+5\times F_{i-4}+8\times F_{i-5}, & (i \ge 6)\\ \end{cases} \end{equation*} Fi ={1,Fi−1 +2×Fi−2 +3×Fi−3 +5×Fi−4 +8×Fi−5 , 1≤(i≤5)(i≥6)
求 AnsAnsAns，其中：
Ans={FNmod 232,FNmod 232<231(FNmod 232)−232,FNmod 232≥231\begin{equation*} Ans= \begin{cases} F_N\mod 2^{32}, & F_N\mod 2^{32}\lt 2^{31}\\ (F_N\mod 2^{32})-2^{32}, & F_N\mod 2^{32}\ge 2^{31}\\ \end{cases} \end{equation*} Ans={FN mod232,(FN mod232)−232, FN mod232<231FN mod232≥231
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
暴力代码
很显然的一个递推式子。直接模拟一下即可。
时间复杂度：O(TN)O(TN)O(TN)
空间复杂度：O(N)O(N)O(N)
预计得分：30pts30pts30pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
空间优化
显然 dpidp_idpi 只与 dpi−1,dpi−2,dpi−3,dpi−4,dpi−5dp_{i-1},dp_{i-2},dp_{i-3},dp_{i-4},dp_{i-5}dpi−1 ,dpi−2 ,dpi−3 ,dpi−4 ,dpi−5 有关。所以我们只需要记录 666 个数即可。
时间复杂度：O(TN)O(TN)O(TN)
空间复杂度：O(1)O(1)O(1)
预计得分：30pts30pts30pts
正解
由线性递推联想到矩阵加速。
回忆一下斐波那契数列的矩阵加速：定义矩阵：
[FnFn−1]\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} [Fn Fn−1 ]
得到：
M×[Fn−1Fn−2]=[FnFn−1]M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} =\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} M×[Fn−1 Fn−2 ]=[Fn Fn−1 ]
根据矩阵乘法，得到：
M1,1×Fn−1+M1,2×Fn−2=FnM2,1×Fn−1+M2,2×Fn−2=Fn−1M_{1,1} \times F_{n-1}+ M_{1,2} \times F_{n-2} = F_n \\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} = F_{n-1} M1,1 ×Fn−1 +M1,2 ×Fn−2 =Fn M2,1 ×Fn−1 +M2,2 ×Fn−2 =Fn−1
所以得到：
M=[1110]M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} M=[11 10 ]
于是问题转化为：
[11]×Mn−1\begin{bmatrix} 1 \\ 1 \end{bmatrix} \times M^{n-1} [11 ]×Mn−1
矩阵快速幂即可。
类似地，我们定义矩阵：
[FnFn−1Fn−2Fn−3Fn−4]\begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix} Fn Fn−1 Fn−2 Fn−3 Fn−4
得到：
M×[Fn−1Fn−2Fn−3Fn−4Fn−5]=[FnFn−1Fn−2Fn−3Fn−4]M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \\ F_{n-5} \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix} M× Fn−1 Fn−2 Fn−3 Fn−4 Fn−5 = Fn Fn−1 Fn−2 Fn−3 Fn−4
根据矩阵乘法，得到：
M1,1×Fn−1+M1,2×Fn−2+M1,3×Fn−3+M1,4×Fn−4+M1,5×Fn−5=FnM2,1×Fn−1+M2,2×Fn−2+M2,3×Fn−3+M2,4×Fn−4+M2,5×Fn−5=Fn−1M3,1×Fn−1+M3,2×Fn−2+M3,3×Fn−3+M3,4×Fn−4+M3,5×Fn−5=Fn−2M4,1×Fn−1+M4,2×Fn−2+M4,3×Fn−3+M4,4×Fn−4+M4,5×Fn−5=Fn−3M5,1×Fn−1+M5,2×Fn−2+M5,3×Fn−3+M5,4×Fn−4+M5,5×Fn−5=Fn−4M_{1,1} \times F_{n-1} + M_{1,2}
\times F_{n-2} + M_{1,3} \times F_{n-3} + M_{1,4} \times F_{n-4} + M_{1,5} \times F_{n-5}=F_n\\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} + M_{2,3} \times F_{n-3} + M_{2,4} \times F_{n-4} + M_{2,5} \times F_{n-5}=F_{n-1}\\ M_{3,1} \times F_{n-1} + M_{3,2} \times F_{n-2} + M_{3,3} \times
F_{n-3} + M_{3,4} \times F_{n-4} + M_{3,5} \times F_{n-5}=F_{n-2}\\ M_{4,1} \times F_{n-1} + M_{4,2} \times F_{n-2} + M_{4,3} \times F_{n-3} + M_{4,4} \times F_{n-4} + M_{4,5} \times F_{n-5}=F_{n-3}\\ M_{5,1} \times F_{n-1} + M_{5,2} \times F_{n-2} + M_{5,3} \times F_{n-3} + M_{5,4} \times F_{n-4} +
M_{5,5} \times F_{n-5}=F_{n-4} M1,1 ×Fn−1 +M1,2 ×Fn−2 +M1,3 ×Fn−3 +M1,4 ×Fn−4 +M1,5 ×Fn−5 =Fn M2,1 ×Fn−1 +M2,2 ×Fn−2 +M2,3 ×Fn−3 +M2,4 ×Fn−4 +M2,5 ×Fn−5 =Fn−1 M3,1 ×Fn−1 +M3,2 ×Fn−2 +M3,3 ×Fn−3 +M3,4 ×Fn−4 +M3,5 ×Fn−5 =Fn−2 M4,1 ×Fn−1 +M4,2 ×Fn−2 +M4,3 ×Fn−3 +M4,4 ×Fn−4 +M4,5 ×Fn−5 =Fn−3 M5,1 ×Fn−1
+M5,2 ×Fn−2 +M5,3 ×Fn−3 +M5,4 ×Fn−4 +M5,5 ×Fn−5 =Fn−4
所以得到：
M=[1235810000010000010000010]M = \begin{bmatrix} 1 & 2 & 3 & 5 & 8\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ \end{bmatrix} M= 11000 20100 30010 50001 80000
于是问题转化为：
Mn−5×[11111]M^{n-5} \times \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix} Mn−5× 11111
矩阵快速幂即可。
时间复杂度：O(TlogN)O(T \log N)O(TlogN)
空间复杂度：O(1)O(1)O(1)
预计得分：100pts100pts100pts
