T4_拆卸爆能器 题解
对于题目里面那张图片，设左边的叫A拼图，右边的叫B拼图。
测试点 1∼2,3∼51\SIM 2,3\SIM 51∼2,3∼5
考虑朴素 dpdpdp。定义 dp(i)dp(i)dp(i) 表示放满 2×i2\times i2×i 的方格的方案数。
考虑手玩多出的第 iii 列的摆法来转移，有如下方案：
第 iii 列直接竖着摆A
有方案数 dp(i−1)dp(i-1)dp(i−1)
* 第一行横着放A，第二行也横着放A
有方案数 dp(i−2)dp(i-2)dp(i−2)
有放B的情况
此时一定是左右放B，中间插入若干个A，如下图
这样的方案数是
∑j=0i−3dpj\sum_{j=0}^{i-3} dp_j j=0∑i−3 dpj
然后把图片中两种情况垂直翻转后依旧成立，所以方案数 ×2\times 2×2，得到转移
dpi=dpi−1+dpi−2+2∑j=0i−3aidp_i=dp_{i-1}+dp_{i-2}+2\sum\limits_{j=0}^{i-3} a_idpi =dpi−1 +dpi−2 +2j=0∑i−3 ai
这个转移是 O(n2)O(n^2)O(n2) 的，可以通过测试点 1∼21\sim 21∼2。但是 dpjdp_jdpj 总和的计算可以用前缀和来优化成 O(1)O(1)O(1)，这样就一并通过了测试点 3∼53\sim 53∼5。
时间复杂度：O(Tn)O(Tn)O(Tn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
测试点 6∼106\SIM 106∼10
请选手先自行学习：“矩阵快速幂”
考虑如下矩阵的转移，sss 表示 dpdpdp 数组的前缀和：
[dpi−1dpi−2si−3]→[dpidpi−1dpi−2]\begin{align*} \begin{bmatrix} dp_{i-1} \\ dp_{i-2} \\ s_{i-3} \end{bmatrix} \rightarrow \begin{bmatrix} dp_i \\ dp_{i-1} \\ dp_{i-2} \end{bmatrix} \end{align*} dpi−1 dpi−2 si−3 → dpi dpi−1 dpi−2
* dpi=dpi−1+dpi−2+2∑j=0i−3aidp_i=dp_{i-1}+dp_{i-2}+2\sum\limits_{j=0}^{i-3} a_idpi =dpi−1 +dpi−2 +2j=0∑i−3 ai
得到矩阵系数 [1 1 2][1\ 1\ 2][1 1 2]
* dpi−1=dpi−1dp_{i-1}=dp_{i-1}dpi−1 =dpi−1
得到矩阵系数 [1 0 0][1\ 0\ 0][1 0 0]
* si−2=si−3+fi−2s_{i-2}=s_{i-3}+f_{i-2}si−2 =si−3 +fi−2
得到矩阵系数 [0 1 1][0\ 1\ 1][0 1 1]
综上：
[fifi−1si−2]=[112100011]×[fi−1fi−2si−3]\begin{align*} \begin{bmatrix} f_i \\ f_{i-1} \\ s_{i-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix} \times \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ s_{i-3} \end{bmatrix} \end{align*} fi fi−1 si−2 = 110 101 201 × fi−1 fi−2
si−3
于是上矩阵快速幂即可。
时间复杂度：O(Tlogn)O(Tlogn)O(Tlogn)
