递归多项式与Berlekamp-Massey算法在信息学竞赛中的应用

"这篇资源是IOI2017中国国家候选队的论文集，其中包含了一篇由雅礼中学毛啸撰写的论文——《关于数列递归式的一些研究》。论文主要探讨了递归多项式和Berlekamp-Massey算法在信息学竞赛中的应用，特别是对于隐式递归式的研究。" 在《通用解法-ansi-vita 62-2016 modular power supply standard》中，提到的是一个动态规划的通用解法，该方法基于决策单调性。在处理决策问题时，可以使用双端队列来维护决策的有效性。当有新的决策加入时，需要比较它与队尾决策的优劣，如果新的决策优于队尾决策，就从队尾开始退队，直到队尾决策可能成为最优。每次询问时，只需弹出队首已不再是最优的决策。这种方法需要比较O(N)对决策，每对决策的比较可能需要O(log N)的时间复杂度，所以总时间复杂度为O(N log N)。在特定问题中，可以通过改变策略，只在询问时弹出队尾不优的决策，从而优化算法。 在毛啸的论文中，他提出“递归多项式”这一概念，用于处理隐式递归式的问题。递归多项式是一个强大的工具，它在递归式计数和计算稀疏矩阵的特征多项式等方面有应用。论文还提到了Berlekamp-Massey算法，这是一个在信息学竞赛中相对冷门但非常有用的算法。通常，人们对这个算法的了解仅限于将其作为解决问题的捷径，但实际上，它有更广泛的应用价值。通过介绍这两个主题，论文旨在拓宽读者对递归和算法的理解。 Berlekamp-Massey算法是一个在序列分析和编码理论中用于找到最简线性反馈移位寄存器（LFSR）的算法。在信息学竞赛中，它可以用来解决涉及线性递推关系的问题，尽管它在竞赛题目中并不常见。通过深入理解和应用这个算法，可以帮助参赛者解决一些复杂的问题。 这两个资源分别涵盖了动态规划的通用策略和数列递归式的理论研究，都对提高信息学竞赛选手的解决问题能力具有重要的指导意义。