这道题可以发现 NNN 很小，但也没小到那种程度，注意到这题刚刚好能通过 O(N3)O(N^3)O(N3) 的算法。
而且 MMM 又这么大……还是递推题……
这就需要矩阵快速幂了。
由于矩阵乘法符合结合律，所以快速幂也适用于矩阵。这题就是一个很好的示例。
我们可以分别对于 N=4,N=5N=4,N=5N=4,N=5 的情况构造矩阵，然后寻找规律。
任务：构造一个 3×33\times 33×3 的矩阵，使得该矩阵乘以 [A3,i−1A2,i−1A1,i−1]\begin{bmatrix} A_{3,i-1}\\A_{2,i-1}\\A_{1,i-1} \end{bmatrix} A3,i−1 A2,i−1 A1,i−1 得到 [A3,iA2,iA1,i].\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i} \end{bmatrix}. A3,i A2,i A1,i .
1. 化简结果矩阵，直到每一项可以用原矩阵里面的数乘以一个常数的和表示。
[A3,iA2,iA1,i]=[S×A2,i+T×A3,i−1S×A1,i+T×A2,i−1S×A0,i+T×A1,i−1]=[T×A3,i−1+S×T×A2,i−1+S2×T×A1,i−1+S3×i T×A2,i−1+S×T×A1,i−1+S2×i T×A1,i−1+S×i]\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i} \end{bmatrix}
=\begin{bmatrix} S\times A_{2,i}+T\times A_{3,i-1}\\S\times A_{1,i}+T\times A_{2,i-1}\\S\times A_{0,i}+T\times A_{1,i-1} \end{bmatrix} = \begin{bmatrix} T\times A_{3,i-1}+S\times T\times A_{2,i-1}+ S^2\times T\times A_{1,i-1}+S^3\times i\\\space \space \space \space \space \space \space \space
\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space T\times A_{2,i-1}+S\times T\times A_{1,i-1}+S^2\times i\\\space \space \space \space \space \space \space \space \space \space
\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space
\space \space \space \space \space \space \space T\times A_{1,i-1}+S\times i \end{bmatrix} A3,i A2,i A1,i = S×A2,i +T×A3,i−1 S×A1,i +T×A2,i−1 S×A0,i +T×A1,i−1 = T×A3,i−1 +S×T×A2,i−1 +S2×T×A1,i−1 +S3×i T×A2,i−1 +S×T×A1,i−1
+S2×i T×A1,i−1 +S×i
但这里出现了一个问题：iii 不是常数，也不能用前面的矩阵表示！
这也不是没有办法，在目标矩阵加两项：iii 和 111 就行了！
现在的任务：构造一个 5×55\times 55×5 的矩阵，使得该矩阵乘以 [A3,i−1A2,i−1A1,i−1i−11] \begin{bmatrix} A_{3,i-1}\\A_{2,i-1}\\A_{1,i-1}\\i-1\\1 \end{bmatrix} \space A3,i−1 A2,i−1 A1,i−1 i−11 得到 [A3,iA2,iA1,ii1].\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i}\\i\\1 \end{bmatrix}. A3,i A2,i A1,i i1 .
1. 化简结果矩阵……
[A3,iA2,iA1,ii1]=[T×A3,i−1+S×T×A2,i−1+S2×T×A1,i−1+S3×(i−1)+S3 T×A2,i−1+S×T×A1,i−1+S2×(i−1)+S2 T×A1,i−1+S×(i−1)+S(i−1)+11]\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i}\\i\\1 \end{bmatrix} = \begin{bmatrix} T\times
A_{3,i-1}+S\times T\times A_{2,i-1}+ S^2\times T\times A_{1,i-1}+S^3\times (i-1)+S^3\\\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space
\space \space T\times A_{2,i-1}+S\times T\times A_{1,i-1}+S^2\times (i-1)+S^2\\\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space
\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space T\times A_{1,i-1}+S\times (i-1)+S\\(i-1)+1\\1 \end{bmatrix} A3,i A2,i A1,i i1 = T×A3,i−1
+S×T×A2,i−1 +S2×T×A1,i−1 +S3×(i−1)+S3 T×A2,i−1 +S×T×A1,i−1 +S2×(i−1)+S2 T×A1,i−1 +S×(i−1)+S(i−1)+11
OK！
2. 解方程！
设我们构造出的矩阵为 [a1b1c1d1e1a2b2c2d2e2a3b3c3d3e3a4b4c4d4e4a5b5c5d5e5].\begin{bmatrix} a_1 & b_1 & c_1 & d_1 & e_1\\a_2 & b_2 & c_2 & d_2 & e_2\\a_3 & b_3 & c_3 & d_3 & e_3\\a_4 & b_4 & c_4 & d_4 & e_4\\a_5 & b_5 & c_5 & d_5 & e_5 \end{bmatrix}. a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 d1 d2 d3 d4 d5
e1 e2 e3 e4 e5 .
根据矩阵乘法的定义，有：
{a1×A3,i+b1×A2,i+c1×A1,i+d1×(i−1)+e1×1=T×A3,i−1+S×T×A2,i−1+S2×T×A1,i−1+S3×(i−1)+S3,a2×A3,i+b2×A2,i+c2×A1,i+d2×(i−1)+e2×1=T×A2,i−1+S×T×A1,i−1+S2×(i−1)+S2,a3×A3,i+b3×A2,i+c3×A1,i+d3×(i−1)+e3×1=T×A1,i−1+S×(i−1)+S,a4×A3,i+b4×A2,i+c4×A1,i+d4×(i−1)+e4×1=i,a5×A3,i+b5×A2,i+c5×A1,i+d5×(i−1)+e5×1=1.\begin{cases}
a_1\times A_{3,i}+b_1\times A_{2,i}+c_1\times A_{1,i}+d_1\times(i-1)+e_1\times 1=T\times A_{3,i-1}+S\times T\times A_{2,i-1}+ S^2\times T\times A_{1,i-1}+S^3\times (i-1)+S^3,\\ \\ a_2\times A_{3,i}+b_2\times A_{2,i}+c_2\times A_{1,i}+d_2\times(i-1)+e_2\times 1=T\times A_{2,i-1}+S\times T\times
A_{1,i-1}+S^2\times (i-1)+S^2,\\ \\ a_3\times A_{3,i}+b_3\times A_{2,i}+c_3\times A_{1,i}+d_3\times(i-1)+e_3\times 1=T\times A_{1,i-1}+S\times (i-1)+S,\\ \\ a_4\times A_{3,i}+b_4\times A_{2,i}+c_4\times A_{1,i}+d_4\times(i-1)+e_4\times 1=i,\\ \\ a_5\times A_{3,i}+b_5\times A_{2,i}+c_5\times
A_{1,i}+d_5\times(i-1)+e_5\times 1=1. \end{cases} ⎩⎨⎧ a1 ×A3,i +b1 ×A2,i +c1 ×A1,i +d1 ×(i−1)+e1 ×1=T×A3,i−1 +S×T×A2,i−1 +S2×T×A1,i−1 +S3×(i−1)+S3,a2 ×A3,i +b2 ×A2,i +c2 ×A1,i +d2 ×(i−1)+e2 ×1=T×A2,i−1 +S×T×A1,i−1 +S2×(i−1)+S2,a3 ×A3,i +b3 ×A2,i +c3 ×A1,i +d3 ×(i−1)+e3 ×1=T×A1,i−1 +S×(i−1)+S,a4
×A3,i +b4 ×A2,i +c4 ×A1,i +d4 ×(i−1)+e4 ×1=i,a5 ×A3,i +b5 ×A2,i +c5 ×A1,i +d5 ×(i−1)+e5 ×1=1.
一一对应即可，可以轻松获得方程的解。
最终获得的矩阵为
[TS×TS2×TS3S30TS×TS2S200TSS0001100001].\begin{bmatrix} T & S\times T & S^2\times T & S^3 & S^3\\ 0 & T & S\times T & S^2 & S^2\\ 0 & 0 & T & S & S\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}. T0000 S×TT000 S2×TS×TT00 S3S2S10 S3S2S11 .
对于 N=5N=5N=5 的情况，你们可以自己试一下，最终构造出的矩阵为
[TS×TS2×TS3×TS4S40TS×TS2×TS3S300TS×TS2S2000TSS000011000001].\begin{bmatrix} T & S\times T & S^2\times T & S^3\times T & S^4 & S^4\\ 0 & T & S\times T & S^2\times T & S^3 & S^3\\ 0 & 0 & T & S\times T & S^2 & S^2\\ 0 & 0 & 0 & T & S & S\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}.
T00000 S×TT0000 S2×TS×TT000 S3×TS2×TS×TT00 S4S3S2S10 S4S3S2S11 .
我们发现，最后一行只有最后一列是 111，其余都是 000；第 NNN 行只有后两列是 111，其余都是 000。
对于第 i(1≤i≤N)i(1\le i\le N)i(1≤i≤N) 行，第 iii 列为 TTT，其余的均为下一行乘以 SSS。
构造方法如下：
初始矩阵：
[⋮A3,0A2,0A1,001].\begin{bmatrix} \vdots\\ A_{3,0}\\A_{2,0}\\A_{1,0}\\0\\1 \end{bmatrix}. ⋮A3,0 A2,0 A1,0 01 .
然后就可以快速幂了。
矩阵快速幂和普通快速幂差不多，但注意矩阵乘法不满足交换律，所以顺序不能搞混！
时间复杂度 O(QN3logM)O(QN^3\log M)O(QN3logM)。
初次推矩阵耗时可能长一些，但熟练之后两三分钟就可以完成了。加油！
