RT，模拟赛的一道题，大致意思如下：

给定正整数 $n,m$ 和一个二维矩阵 $b_{m, m}$ ，需要构造出一个长度为 $n + 1$ 的数列 $a_0, a_1 \dots a_n$，满足任意 $a_i \in [1, m]$。定义该数列的价值为 $\sum\limits_{i=1}^{n} b_{a_{i-1},a_i}$，求出最大价值。

数据范围：$n \le 10^{15}, m \le 100, b_{i, j} \le 10$。

赛时想到了 DP。用 $f_{i,j}$ 表示填了数列的前 $i$ 位，且第 $i$ 位填 $j$ 的最大价值。转移方程：$f_{i,j} = \max \{f_{i-1,k}+b_{k,j} \}$，直接 $\Theta(nm^2)$ 转移。

赛后有大佬说用矩阵加速，但是本蒟蒻只学过求和类的矩阵加速，没学过最值类的。求大佬！