rt，觉得可以区间打表，尝试一下发现过了，但题解里都是矩阵dp的做法，不知道能不能加上区间打表的非主流做法（雾）