题解 AT_abc388_f

设 $dp_i$ 表示能否到达 $i$，有转移 $dp_i=\operatorname{OR}\limits_{⁡j=a}^b dp_{i−j}$ 且 $i$ 不是坏的。

直接矩阵快速幂优化即可，总复杂度 $O(mb^3\log⁡n)$。

套路地注意到初始矩阵是行向量，行向量乘什么玩意都是行向量，所以快速幂时只转移第一行即可。总复杂度 $O(mb^2\log⁡n)$。

在 sunkuangzheng 大佬的提示下注意到矩阵大小只有 $20$ 且值只有 $0/1$，所以可以压位。总复杂度 $O(mb\log n)$。code。

为啥跑的更慢了。

upd: 前两天又学会了点东西。注意到预处理和查询的复杂度不平衡，考虑更换 $\log$ 的底数来平衡复杂度，可以使复杂度进一步更优，复杂度具体是啥要看你取的底数，算算最优的是多少就行了。类似于多叉线段树的思想。