2020牛客暑期多校训练营首讲：B-SuffixArray与相关算法详解

本篇笔记是关于2020年牛客暑期多校训练营的第一场课程讲解，由郭晓絮主讲。主要讨论了两个核心主题： 1. **B-Suffix Array (B-后缀数组)**: - B-Suffix Array是一种数据结构，它与普通的后缀数组类似，但通过定义新的字符序列C_i，其中C_i是所有比i大的索引j对应的字符串s_j中最短且与s_i相同的子串的长度。其构建原理可以参考"Parameterized Suffix Arrays for Binary Strings"（2008年Stringology会议论文）。 - 计算B-Suffix Array的过程等价于对C_1C_2C_n进行普通后缀数组的构建。 2. **Infinite Tree and Cost Computation**: - 针对一个特定问题，首先计算阶乘序列{1!, 2!, ..., n!}的“虚拟树”，这有助于理解问题的结构。 - 然后利用段树或 Fenwick Tree 实现实际成本的计算，时间复杂度为 O(mlog^2m)，其中m可能代表序列的长度。 3. **Exponential Function and Matrix Inverse**: - 接下来讨论的是指数函数的使用，特别是求解一个特定形式的矩阵问题，即求解b^TA^{-1}b，这里A是系数矩阵。利用拉格朗日对偶性进行证明，并强调了计算逆矩阵A的重要性。 4. **Counting Spanning Trees (树的数量计算)**: - 讲解如何计算图中spanning trees（生成树）的数量，给出公式为prod_{i>=2}deg(x_i)deg(y_i)，其中deg表示节点的度数。这个概念在组合数学和图论中有应用，详细证明可见"Enumerative properties of Ferrers graphs"（2007年arXiv预印本）。 5. **Additional Topics**: - 笔记还涉及到其他问题，如 Domino Flip Graphs中的距离计算、Quadratic Form（二次型）问题以及一个矩阵运算示例。但具体内容没有详细列出，只提及了相关的文献来源。 这些知识点展示了在2020牛客暑期多校训练营中，课程内容涵盖了字符串处理、图论、线性代数等基础IT领域的深入讨论，对于参与该训练营的学生来说，提供了理论和实践相结合的学习材料。