CSL ACM模板：数学与字符串处理精华

"这是一份来自上海大学CSL团队的大佬级别的ACM竞赛模板手册，涵盖了数学、字符串处理等多个竞赛中常用的知识点和技术。" 在ACM/ICPC竞赛中，掌握高效算法和数据结构是关键。这份模板手册详细介绍了以下几个方面： 1. **数学**： - **素数**：包括埃拉托斯特尼筛法（Eratosthenes Sieve）、欧拉筛法（Eular Sieve）、质因数分解、米勒-拉宾素性检验（Miller-Rabin）以及区间筛法（Segment Sieve）。 - **欧拉φ函数**：讨论了欧拉函数的计算方法和基于筛法的实现。 - **基础数论**：涉及扩展欧几里得算法（Extended Euclidean Algorithm）、线性同余方程的解法、模逆元的求解。 - **模线性方程**：涵盖中国剩余定理（Chinese Remainder Theorem）及其扩展（ExCRT）。 - **组合数学**：包括组合计算、Lucas定理、大数组合及波利亚计数。 2. **快速幂运算**：一种用于快速计算幂次的算法。 3. ** Möbius 反演**：涉及Möbius函数及其应用，如计算互质对的数量以及可见树问题。 4. **快速变换**：包括快速傅里叶变换（FFT）、数域快速傅里叶变换（NTT）以及傅里叶–华（FWT）变换，这些在多项式计算和数论问题中非常有用。 5. **数值积分**：介绍自适应辛普森法则（Adaptive Simpson's Rule）和贝雷坎普-马斯赛算法（Berlekamp-Massey）。 6. **字符串处理**： - **KMP算法**：一种高效的字符串匹配算法。 - **扩展KMP**：KMP的改进版本，能处理更复杂的模式匹配问题。 - **Manacher算法**：用于找到字符串中的最长回文子串。 - **Aho-Corasick自动机**：一次遍历字符串，同时找出所有模式匹配的位置。 - **后缀数组**：用于快速查找字符串的后缀，常用于字符串问题的解决。 - **其他未列出的字符串处理技术**：手册可能还包含更多字符串相关的高级算法。 这份手册不仅是ACM竞赛选手的重要参考资料，也是学习算法和数据结构的宝贵资源。它详尽地介绍了多个竞赛中常用的技术，对于提升编程能力和解决复杂问题的能力大有裨益。