有趣的矩阵乘法

(为方便,下文中“大号宝石”代指连续的$m$个分裂出来的宝石,“小号宝石”代指未分裂的单个宝石)

首先,我们观察这题,考虑$DP​$,设状态$f_i​$表示已经取了$i​$个单元的方案数的不难推出一个朴素的$O(n^2) DP​$方程$f_i = \displaystyle\sum_{i - j \geq m} f_j +1​$(可以理解成上一个大号宝石放的位置,最后一个$1​$即为全部用小号宝石填满的方案)

我们再仔细看看这个式子,加个前缀和,不难优化到$O(n)$,然而数据范围$n \leq 10^{18}$,这让我们考虑$O(\log n)$级别的算法,我们接下来考虑矩阵乘法优化这个式子。