T1:传球游戏

思考难度:提高?

代码难度:提高?

正解:矩阵快速幂

若令 f [ i ] [ j ] f[i][j] f[i][j]为第 i i i次传传到第 j j j个人的方案数,易知 f [ i ] [ j ] = f [ i 1 ] [ j 1 ] + f [ i 1 ] [ j + 1 ] f[i][j]=f[i-1][j-1]+f[i-1][j+1] f[i][j]=f[i1][j1]+f[i1][j+1]

但是直接这样递推 O ( n m ) O(nm) O(nm) T L E TLE TLE,于是想到用矩阵来加速递推。

可知初始矩阵中 a n s [ i ] [ i ] = 1 ans[i][i]=1 ans[i][i]=1,递推矩阵中 a [ 0 ] [ n 1 ] = a [ n 1 ] [ 0 ] = 1 a[0][n-1]=a[n-1][0]=1 a[0][n1]=a[n1][0]=1 a [ i ] [ i + 1 ] = a [ i ] [ i 1 ] = 1 a[i][i+1]=a[i][i-1]=1 a[i][i+1]=a[i][i1]=1。进行快速幂即可,时间复杂度 O ( n 3 × l o g   m ) O(n^3\times log\:m) O(n3×logm),时间、空间都不允许。

但是,我们通过观察发现,无论何时,矩阵都是循环的,即
A = ( <mstyle displaystyle="false" scriptlevel="0"> a 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 3 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a n </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a n </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a n 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a n 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a n </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a n 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 3 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 4 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a 1 </mstyle> ) A=\begin{pmatrix} a_1 &amp; a_2 &amp; a_3 &amp; \cdots &amp; a_n \\ a_n &amp; a_1 &amp; a_2 &amp; \cdots &amp; a_{n-1} \\ a_{n-1} &amp; a_n &amp; a_1 &amp; \cdots &amp; a_{n-2} \\ \vdots &amp; \vdots &amp; \vdots &amp; &amp; \vdots \\ a_2 &amp; a_3 &amp; a_4 &amp; \cdots &amp; a_1 \\ \end{pmatrix} A=a1anan1a2a2a1ana3a3a2a1a4anan1an2a1

我们利用此性质。乘出矩阵的一行来,直接将其他的复制好,时间复杂度 O ( n 2 × l o g &MediumSpace; m ) O(n^2\times log\:m) O(n2×logm),时间复杂度符合要求,但空间超了。

于是我们将矩阵缩为一维,利用循环的性质来求值即可,空间复杂度将为 O ( n ) O(n) O(n),理论上可以通过本题,但还是TLE。(18.19点2500ms+)

再来观察矩阵,发现第一行是

a 1 &ThickSpace;&ThickSpace; a 2 &ThickSpace;&ThickSpace; a 3 &ThickSpace;&ThickSpace; &ThickSpace;&ThickSpace; a n + 1 2 1 &ThickSpace;&ThickSpace; a n + 1 2 &ThickSpace;&ThickSpace; a n + 1 2 1 &ThickSpace;&ThickSpace; &ThickSpace;&ThickSpace; a 3 &ThickSpace;&ThickSpace; a 2 a_1\;\;a_2\;\;a_3\;\;\cdots\;\;a_{\lfloor{\frac{n+1}{2}\rfloor}-1}\;\;a_{\lfloor{\frac{n+1}{2}\rfloor}}\;\;a_{\lfloor{\frac{n+1}{2}\rfloor}-1}\;\;\cdots\;\;a_3\;\;a_2 a1a2a3a2n+11a2n+1a2n+11a3a2

(偶数自行脑补)

即对称,所以可以优化一半常数。

但还是TLE。。。(18.19点1500ms+)

我们继续优化,发现矩阵相乘时,若有0,直接跳过,又优化了一点。(18.19点950~1100ms)

考虑观察一行,发现计算每一个的时候有重复计算的,我们发现可以用左面对称和右面对称来计算,还要考虑n为奇数偶数情况,及i为奇数偶数情况,可优化一半常数(理论上)。

于是就可以700ms通过本题了。(无 O 2 &ThickSpace;&ThickSpace; O 3 O_2\;\;O_3 O2O3)