「清华集训 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

\[ \ \]

Part2

对于已知 \(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\) 较小的情况下，实际运行总能有更好的表现