T1:传球游戏

思考难度：提高?

代码难度：提高?

正解：矩阵快速幂

若令f[i][j]f[i][j]f[i][j]为第iii次传传到第jjj个人的方案数，易知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[i−1][j−1]+f[i−1][j+1]

但是直接这样递推O(nm)O(nm)O(nm)会TLETLETLE，于是想到用矩阵来加速递推。

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

但是，我们通过观察发现，无论何时，矩阵都是循环的，即
A=(a1a2a3⋯anana1a2⋯an−1an−1ana1⋯an−2⋮⋮⋮⋮a2a3a4⋯a1)A=\begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_n \\ a_n & a_1 & a_2 & \cdots & a_{n-1} \\ a_{n-1} & a_n & a_1 & \cdots & a_{n-2} \\ \vdots & \vdots & \vdots & & \vdots \\ a_2 & a_3 & a_4 & \cdots & a_1 \\ \end{pmatrix}A=⎝⎜⎜⎜⎜⎜⎛​a1​an​an−1​⋮a2​​a2​a1​an​⋮a3​​a3​a2​a1​⋮a4​​⋯⋯⋯⋯​an​an−1​an−2​⋮a1​​⎠⎟⎟⎟⎟⎟⎞​

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

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

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

a1    a2    a3    ⋯    a⌊n+12⌋−1    a⌊n+12⌋    a⌊n+12⌋−1    ⋯    a3    a2a_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_2a1​a2​a3​⋯a⌊2n+1​⌋−1​a⌊2n+1​⌋​a⌊2n+1​⌋−1​⋯a3​a2​

(偶数自行脑补)

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

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

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

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

于是就可以700ms通过本题了。(无O2    O3O_2\;\;O_3O2​O3​)