「清华集训 2017」小 Y 和恐怖的奴隶主

~~是不是这题太水了都没人写啊~~

本题官方题解提供的做法实际上复杂度非常高

Part1

很显然本题的$\text{dp}$是存储每种血量的随从数量

设状态数量的上限是$S$

当$m=3,k=8$时，这样的状态一共有$S=165+1$种

如果直接$dp$，每次转移是$O(1)$的，可以做到$O(n\cdot S)$，显然无法处理$n$较大的情况

用矩阵优化$\text{dp}$转移，朴素的实现可以做到$O(T\cdot \log n\cdot S^3)$

如果预处理出转移矩阵的幂次，每次查询时只有列向量与方阵的乘法，所以复杂度是$O(\log n\cdot S^3+T\log n\cdot S^2)$

实际极限的复杂度预估在$60\cdot 166^3+500\cdot 60\cdot 166^2\approx 11\cdot 10^8$

官方题解提供的做法就是在在这个算法上进行常数优化，这~~wtm~~

$\$

对于已知$m,k$来说，设每个$n$构成的答案数列为$a_n$

预先处理一部分的答案$a_1\cdots a_n$，使用$\text{Berlekamp-Massey }$算法求出序列的最短线性递推

发现总是在$O(S)$的长度以后，递推序列不再改变，即总能得到一个长度为$O(S)$的全局线性递推

即总可以在$O(S^2)$的时间内求出答案序列$a_n$的线性递推式

那么对于求得的线性递推式，问题转化为对于每个查询的$n$，求常系数线性递推数列的第$n$项答案

用特征多项式的做法，可以做到单组查询$O(S\log n\log S)$的之间求出

那么总复杂度就是$O(S^2+T\cdot S \log S\log n)$

理论上来说，复杂度上限应该只有$166^2+500\cdot 166\cdot 10\cdot 60\approx 0.5\cdot 10^8$

理论上来说，这个复杂度无论是不是渐进意义下都比矩阵快

但是实际实践中，由于多项式运算的大常数，不优秀的实现下甚至可能超时

考虑到本题多查询的性质，我改变了倍增的基数$D$，并且预处理出倍增用到的$x^i\mod \lambda$

预处理部分的复杂度是$O(\log_D^n \cdot (D-1)\cdot S\log S)$

查询部分的复杂度是$O(\log _D^n S\log S)$

~~由于我的多项式模板不够成熟~~

在LOJ上，经过这样的魔改，已经能跑得比矩阵块

但是在UOJ上，我同样的代码竟然慢了四倍，而这份代码在UOJ上的运行时间还略有提高

表示很是绝望。。

事实上，这种做法在$m,k$较大时同样可行，在$S$较大，$T$较小的情况下，实际运行总能有更好的表现