邝斌ACM算法模板2018：字符串处理与数学算法

“kuangbin的ACM模板（2018年7月新版）.pdf”是邝斌大神针对ACM竞赛精心编写的算法模板，包含了2018年7月的更新，修复了之前的一些错误。模板涵盖了字符串处理、数学等多个重要领域，旨在帮助参赛者快速解决各种算法问题。 1. 字符串处理： - KMP算法：一种用于字符串匹配的高效算法，避免了不必要的回溯，提高了查找效率。 - e-KMP：KMP算法的一种优化，通过增加部分表来减少预处理时间。 - Manacher算法：用于求解最长回文子串问题，利用对称性质减少计算量。 - AC自动机：一种字符串搜索的自动机，可以同时处理多个模式串的匹配。 - 后缀数组：用于处理字符串的排序和查询，可以快速找到字符串的所有子串及其出现次数。 - DA（Double Array）：构建后缀数组的一种方法，具有较高的构建速度。 - DC3：用于构建后缀数组的另一种算法，相比DA更节省空间。 - 后缀自动机：后缀数组的扩展，能进行更复杂的字符串操作。 - 字符串Hash：用于快速比较字符串是否相同，常用于文本处理和字符串匹配。 2. 数学： - 素数筛选：包括判断素数、筛选素数和大区间素数筛选的方法。 - 扩展欧几里得算法：求两个整数的最大公约数并找出其解的形式。 - 求逆元：在模运算下求一个数的逆元，常用于数论问题。 - 模线性方程组：解决模意义下的线性方程组问题。 - 随机素数测试和大数分解：用于验证大数的素性及分解大数。 - 欧拉函数：与数的因数分布相关的函数，用于计算群的阶。 - 高斯消元：用于解决线性方程组，包括浮点数的处理。 - FFT（快速傅里叶变换）：用于快速计算离散傅里叶变换，广泛应用于多项式乘法等。 - 方程组的解：包括对2取模的01方程组和同余方程组的解法。 - 整数拆分：将一个整数拆分为若干个正整数的和，研究其组合数。 - 求AB的约数之和对MOD取模：计算两个数乘积的所有约数之和模一个数的结果。 - 莫比乌斯反演：在数论中的一种重要工具，用于简化计算。 - Baby-Step Giant-Step：解决大整数的模幂运算问题。 - 自适应Simpson积分：数值积分的一种方法，根据数据自动调整步长。 - 斐波那契数列取模循环节：研究斐波那契数列模一定数后的周期性。 - 原根：在模p意义下，满足某个条件的整数，用于计算模幂运算。 - 快速数论变换：类似FFT，用于模运算下的多项式乘法和除法。 这份模板详细地列举了ACM竞赛中常见的算法和技巧，对于参赛者来说是一份宝贵的参考资料，可以帮助他们在比赛中快速解决问题，提高解题效率。