U149068 这次是四阶 题解
原文创建时间：2021-03-05 20:22:23
题目链接
题意
定义数列 $a$，满足
$$\displaylines{a_i = \begin{cases}
6 & (i = 1)\\
3 & (i = 2)\\
5 & (i = 3)\\
8 & (i = 4)\\
a_{i-4} + a_{i-1} - 7 & (i > 4,\ i\equiv1\pmod{2})\\
a_{i-4} + a_{i-1} + 1 & (i > 4,\ i\equiv0\pmod{2})
\end{cases}}$$
给出 $k(k \leq 10^{16})$，求出 $a_k$ 的值，答案对 $998,244,353$ 取模。
多组询问，询问组数不多于 $10^3$ 组。
题解—搬运
由递推形式和数据范围，可以想到通过构造矩阵来快速计算。
考虑如何处理奇偶项交替的 $-7$ 和 $+1$。
我们可以将其变换为 $-3 \pm 4$，从而 $i > 4$ 时 $a_i$ 的表达式可以写作
$$a_i = a_{i-4} + a_{i-1} - 3 + 4 \times (-1)^i$$
接下来可以依此构造矩阵。列出方程组求解。
这里的做法是设计如下两个矩阵：
$$\displaystyle A = \left[\begin{matrix}6&3&5&8&-3&-4\end{matrix}\right]$$
$$\displaylines{T = \left[\begin{matrix}
0&0&0&1&0&0\\
1&0&0&0&0&0\\
0&1&0&0&0&0\\
0&0&1&1&0&0\\
0&0&0&1&1&0\\
0&0&0&1&0&-1
\end{matrix}\right]}$$
则数列第 $i (i > 4)$ 项的值即为 $A \times T^{i-4}$ 的第 $4$ 项。
单组数据时间复杂度： $\mathrm{O} \left(6^3\log k\right)$
代码
略。
关于题目难度
个人认为难度大概是绿。欢迎提供您的评分（黄 ~ 蓝）。