rt， 已过，但是不是很理解部分分的配置：

官方题解中提到

• 前几个 Subtask 部分可以使用暴力、动态规划与矩阵快速幂优化动态规划解决，在此不一一阐述。

dp如何解决 $n , k \leq 1000$ 的问题？

直接 $dp_{i,j}$ 是 $O(n^2k^2)$ 的吧，优化方式好像也只有写成一个类似二维卷积的式子。 矩阵快速幂又是什么配置，不太理解。