信息学中的分块思想.pdfVIP

信息学中的分块思想 成都七中 2013 级13 班 王 迪 信息学中的分块思想 成都七中 2013 级13 班 王 迪 摘要：本文主要研究了分块思想在信息学竞赛的数论和数据结构两方面的应用。 关键词：信息学 分块 数据结构 块状数组 块状链表 目录 ○ 前言 第 1 页 ○ 分块思想在数论中的应用 第 2 页 ○ 分块思想在数据结构中的应用 第 2 页 ○ 块状数组 第 2 页 ○ 块状链表 第 6 页 ○ 总结 第 12 页 ○ 参考文献 第 13 页 ○ 特别感谢 第 13 页 ○ 前言 Pascal 之父尼古拉斯·沃斯凭借这样一句话获得图灵奖：“算法+数据结构＝ 程序。”对于数据结构，从链表、栈、队列、二叉堆、二叉查找树，到二项堆、 左偏树、斐波那契堆、AVL、SBT、Treap、伸展树、红黑树、线段树、矩形树， 形形色色，花样百出，让人应接不暇。而随着数据结构的发展，我们不仅能够更 好的驾驭计算机解决现实问题，还能更加深刻的感受到算法的博大与优美。 我的这篇论文从算法和数据结构两方面介绍了分块的思想，着重介绍分块思 想在数据结构中的应用。所谓分块，就是将规模为 的问题划分为块，每块规模 为 ，那么对块内的操作和整个范围内的操作的复杂度要平均，即令 = = √。 通过这个思想可以把()的复杂度降到(√) ，达到优化算法的目的。 1 信息学中的分块思想 成都七中 2013 级13 班 王 迪 ○ 分块思想在数论中的应用 【问题1 】求解 ≡ ( )的最小非负整数解。（数据保证1 ≤ , , ≤ 109 ， 为质数） 若为 的倍数，那么无解；若不为 的倍数，由 为质数我们知道与互 0 1 −1 质，那么 , , …, 构成模 的完全剩余系。这样 的范围缩小到0 ≤ ， 通过枚举可以在()的时间内得到解，但因为 的范围很大，暴力枚举会超时。 设 = + (0 ≤ s p) ，那么原来的同余方程可转化为 ≡ × − ( ) ，− 的含义是乘以 的乘法逆元。通过枚举的取值将 ( )的 值用Hash 映射到 ，即( ( )) = ，再通过枚举进行判断。通过 观察可以知道，若 的值过小，那么枚举的时间复杂度偏高；若 的值过大，那 么枚举 的时间开销又太大。那么只有分得尽量均匀才好。那么可以列出下面这 个式子： − 1 = max = max = ⌊( − 1)/⌋ 通过上式我们发现，令 = − 1 是个不错的选择。这样一来，枚举和 的