题解 AT_abc388_f

Le0Chan · 2025-01-14 11:21:52 · 题解

设 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 的底数来平衡复杂度，可以使复杂度进一步更优，复杂度具体是啥要看你取的底数，算算最优的是多少就行了。类似于多叉线段树的思想。