P10528 [XJTUPC2024] 崩坏：星穹铁道 题解

题目大意

给定 $4$ 名角色，有三种不同的行动类型，$n$ 次行动，求有多少种行动方案。

思路

先考虑最基本的动态规划，$f_{i,j}$ 代表第 $i$ 次行动，剩余 $j$ 个战技点的不同方案数。

如果 $a=1$，即当前角色为类型 $1$，若当前战技点满了（$j=5$）不会增加一个战技点，否则会增加，即：

$f_{i,j} = \begin{cases} f_{i-1,j-1} & j>0 \\f_{i-1,5} & j=5\end{cases}$

同理，可得 $a=2$ 和 $a=3$ 时的转移方程：

$f_{i,j} = \begin{cases} f_{i-1,j+1} & j<5 \\f_{i-1,0} & j=1\end{cases}$

$f_{i,j} = \begin{cases} f_{i-1,j-1} & j>0 \\f_{i-1,5} & j=5 \\ f_{i-1,j+1}& j<5 \end{cases}$

发现 $i$ 这一维在转移时只取到了 $i-1$，因此可以使用滚动数组优化，但是 DP 的时间复杂度是 $O(n)$ 的，无法通过 $n\leq 10^{18}$。对于这一部分，需要使用 $O(\log n)$ 的算法，因此想到使用矩阵加速递推。

根据转移方程，可以得到转移矩阵：

若 $a=1$，则转移矩阵为：