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

"这篇论文主要探讨了解决子问题的策略，特别是在ANSI-VITA 62-2016模块化电源标准的上下文中。文章分为三个部分，分别针对不同的子问题限制提出解决方案。 6.1 解决子问题限制1 在这一部分，问题的核心是计算字符串X的本质不同子串的数量。通过构建后缀自动机，我们可以有效地解决这个问题。定义了一些关键术语，如right(p)表示结点p所表示子串的右端点集合，min(p)和max(p)分别表示结点p对应最短和最长子串的长度，fail(p)是失败结点，last(p)是right集合中的最大值。通过枚举后缀自动机的所有结点并累加对应子串数量，可以达到O(Qn)的时间复杂度和O(n)的空间复杂度。 6.2 利用预处理进行优化 针对Q值较大的测试点，原有的方法可能效率不足，因此引入预处理。对于串A[l:r]，其后缀自动机可以通过在A[l:r-1]后面添加字符得到，而统计答案时只需在max和min变化时局部更新。预处理后的每次询问复杂度降为O(1)，总时间复杂度为O(n^2+Q)，空间复杂度为O(n^2)。 6.3 解决子问题限制2 当存在限制2，问题变为求特定子串f(X,Y, �)的数量。此时，仅需计算Head(Y, u)和Tail(X, u)。通过反向处理原串，可以找到以u结尾的本质不同子串。在枚举结点时记录right(p)的一个值，即可确定max(p)-min(p)+1个子串的末尾字符。 此外，该资源还提到了一篇集训队论文，主要讨论了数列递归式的研究，包括递归多项式和Berlekamp-Massey算法。递归多项式是一种新的概念，适用于隐式递归式的处理，而Berlekamp-Massey算法虽然不常见，但具有广泛的应用潜力。论文作者强调这两个主题在信息学竞赛中的重要性和潜在价值，同时给出了相关定义、结论及算法的应用实例。 这篇论文集包含了多个信息学竞赛相关的主题，如数列递归式的计数问题、图匹配、多项式求和等，展现了信息学竞赛中复杂问题的解决思路和技术。"