第8章

本章介绍了很多著名的数列，我认为这是本书最激动人心的一章。

Catalan数：C_n = C(2n,n) / (n+1)；C_n = ΣC_i*C_(n-i)，其中0≤i<n；C_n=C_(n-1)*(4n-2)/(n+1)。它的意义有很多，例如：n+1边形用对角线划分成三角形的方法数；n个+1和n个-1满足所有部分和不小于零的排列数；具有n个节点的二叉树的数量……

对于数列h_i，定义它的（一阶）差分序列Δh_i=h_(n+1)-h_n。它的p阶差分序列就是p-1阶差分序列的差分序列。如果某个序列是n的p次多项式，它的p+1次差分就全是0，p次差分是常数列。利用这个原理可以在给出前n+1项的前提下求解这种序列。差分运算满足对加法的分配率。

序列差分表由它的第0行确定，也就是原序列，但同时也可以由第0条对角线上的元素确定。换句话说，由差分表的第0条对角线就可以确定原序列。有这样两个公式：原序列为h_i，第0条对角线为c_o,c_1,…,c_p,0,0,0,…则h_n = c_0*C(n,0)+c_1*C(n,1)+…+C(n,p)，Σh_k(k=0..n) = c_0*C(n+1,1)+c_2*(n+1,2)+…+c_p*C(n+1,p+1)。记住这两个公式，差分表（的第0条对角线）就变得非常有用了。

第二类Stirling数：S(p,k) = k*S(p-1,k) + S(p-1,k-1)；S(p,0)=0（p≥1），S(p,p)=1。它的意义是将p个元素的集合划分成k个不可辨别的非空集合的方法数。上面的递推式可以用组合证明：一方面，如果将元素1单独拿出来划分成1个集合，那么方法数是S(p-1,k-1)；另一方面，如果元素1所在的集合不止一个元素，那么可以先将剩下的p-1个元素划分好了以后再选一个集合把1放进去，方法数是k*S(p-1,k)；有加法原理得证。第二类Stirling数有公式：S(p,k) = (Σ(-1)^t * C(k,t) * (k-t)^p) / k!，不过看上去好像意义不大，记住一开始的递推式就好了。

Bell数B_p表示将p个元素的集合划分成一些不可辨别的非空集合的方法数，由第二类Stirling数的定义，显然有：B_p = S(p,0) + S(p,1) + …… + S(p,p)。还有一个递推式：B_p = ΣC(p-1,i)B_i（0<=i<p），可以组合证明。

第一类Stirling数s(p,k)满足的递推关系是：s(p,k) =（p-1)*s(p-1,k) + s(p-1,k-1)；初始条件与S(p,k)一样是s(p,0)=0（p≥1），s(p,p)=1。它表示n个物体排成k个非空的循环排列（就是圆圈）的方法数。

第一类和第二类Stirling数事实上的意义比上面讲到的要丰富，它们是P(n,p)与n^p这两组多项式向量空间的基互相表示的系数。哦……这个不理解没关系的。

将整数n写成一个无序的正整数的和式的方法数就是分拆数p_n。p_n相当于方程n*x_n + … + 2*x_2 + 1*x_1 = n的整数解的个数。书中没有给出递推的或者直接计算的式子，只给出了一个生成函数，实际计算的时候加一维用DP求解就好了。

用n个一般位置上的(k-1)维超平面分割k-维空间所成的区域数是h(n,k)=C(n,0)+C(n,1)+…+C(n,k)。一般的推导较繁。

格路径，就是在平面直角坐标系的整点中从一个点到一个点的最短路径。从(0,0)到(p,q)的格路径数是(p+q,p)，因为一共要走p+q步，选择其中p步向上走。下对角线格路径就是从源点到目标点的对角线的上方（不包括线上的点）不可到达时的格路径数。从(0,0)到(n,n)的格路径数就是Catalan数C_n，根据那个+1、-1部分和很容易证明。一般地，从(0,0)到(p,q)的下对角线格路径条数是R(p,q)=C(p+q,q)*(p-q+1)/(p+1)。如果允许对角步进，计算会有点麻烦，给一个公式好了：从(0,0)到(p,q)经过r个对角步进的格路径数K(p,q:rD)=C(p+q-r,(p-r,q-r,r))（这是多项式系数）；如果下对角线，更加麻烦，R(p,q)=K(p,q)*(q-p+1)/(q-r+1)。

大Schroder数R_n就是上面讨论过的R(n,n)，所以R_n=。小Schroder数s_n指给n个数“加括号”的方法，“加括号”的规则是：一个数不能加括号，可以给任意多个数的序列加上一个括号并在之后把它当作一个数处理，整个序列最外面的括号可以省略。有结论R_n=2*s_(n+1)，用生成函数的方法证明。

上面这些东西重要的是掌握思想，特别是组合证明，至于式子的记忆还是次要的。

第10章

变量，显然是程序里最多使用的东西。我认为这是在OI中改善程序清晰度最重要的一个环节。

声明应该尽量靠近变量第一次使用的位置，初始化靠近声明。尽量减少变量的作用域（存活时间），能局部就不要全局，循环变量不在循环体外部使用的话就声明在内部。能采用const的不要采用神秘数值，如果保证只出现一次的话可以例外。不要采用节省一两个字节的奇怪技巧，比如说同一个变量会先后代表两个不同的事物。确保所有声明的变量都有被使用。

并不像伪代码编程过程之类的方法学，这些软件工程技巧都是“零代价”的。所以为何不将它们引入到OI中呢？

第11章

在OI中，关于变量的命名，唯一的目的是保证你自己能够在整个过程中都能完全清晰的理解。可能的情况下让它尽量自描述可以帮助理解。更值得称道的是你自己养成的从不会搞错的根深蒂固的命名规则。“何时采用命名规则”的清单里，没有OI能对上号的。变量名字没有意义(i,j,k)不要紧，值得担心的是变量名字的字面意义和实际用途不一致。

第12章

避免使用神秘数值，说过好多遍了。事实上，一般使用const声明的原因是因为你可以方便地改动它。

整数需要关注的问题是除法和溢出。除法的规则已经了解，溢出的问题需要加强估算。（我还是记不住2 147 483 647这个神秘数……还是(~0)>>1好了。）

浮点数的加减运算也会出问题，在数量级相差巨大的数之间。等量判断的常识应该是众所周知的。

数组中，需要关心的是下标的溢出，以及嵌套循环中的“下标串话(cross-talk)”。

第13章

结构体可以明确数据的关系。例如几个看上去无关的数组其实是在表示一组元素的多个不同属性。这时若定义一个struct，并使用这个struct的数组可以使代码清晰一些，但也会加大代码长度。值得权衡。当它们可能被作为一个整体来使用时，例如交换甚至排序，那么毫无疑问应该用struct了。

指针是令人亦爱亦恨的东西。它的确很方便，能简化一些东西，但也是很多很多错误的源泉。至于指针的理解，呵呵，每一个真正的C程序员都理解的。

把指针操作限制在子程序或类里面我是同意的。不过若一个名为NextLink()的函数的唯一一行就是i=i->next的话，也太形式主义了点。

应该把指针看作更“易碎”的变量来看待。对待变量的原则——声明与初始化与首次使用尽量接近之类——应该更加严格地施加于指针之上。指针的运用还是应该尽量减少，但决不应该“惧怕”到自己用数组模拟一种指针出来，那会能使强类型变弱。当指针仅仅是为了使接受它为参数的子程序能够修改此变量的时候应该使用引用。

全局变量在OI中的地位有点微妙。由于一个OI程序本身研究的是一个很“局部”的问题。所以所有和整个问题相关的变量（比如说输入进来的数据）都可以全局。真正需要避免的是把确实“局部”的东西，例如循环中的i、j、k都弄成全局的。

第7章

（作者太厉害了，竟然举了一个例子就介绍了在书写rountine过程中可能犯的几乎全部错误。）

创建子程序的最初始目的还是为了避免重复，但是在现代编程中，这不是唯一的目的。降低复杂度，更高层次的抽象，隐藏某些信息是目的中最主要的，其它目的也都很有启发性，因为它们可以最明确无误地告诉我们何时使用子程序。

即便一个看上去过于简单没必要写成子程序的操作，只要它确实多次重复，出于更好的（是的，没有最好的）可读性的目的，还是提倡把它写成子程序。另外，短小但重复的代码带来的另一个问题是无法变化。

在子程序的层面，内聚性的意思就是一个子程序里面做的事情应该是彼此紧密相关的。功能上的内聚性是首要的，在OI中我们应该做到一个子程序只做一件事。

子程序的名字很重要，虽然在OI中似乎不用拘泥什么规则，但最好还是形成自己固定且清晰的命名习惯。当你发现你不能用简短清晰的名字说明子程序所作的事情时，这个子程序的设计大概有问题，比如说有副作用。

也许子程序的长度是一个有意思的研究领域，但是在OI中大约还没有真正“长”的子程序。我近来不喜欢在OI中为子程序而子程序的做法，也就是说任何程序都有Input、Solve、Output这样的子程序（我以前这么做）。我现在认为在OI中不重复的代码完全没必要做子程序。

对于参数表的参数顺序，首要原则我认为是重要的变量放在前面，同时参数列表相似的子程序其顺序应该一致。

函数（在C-like的语言中，特指非void函数）的返回值在某些执行路径中可能会忘记返回值，g++对此也没警告。这是我经常犯的错误……很多时候都会为此调试半天……一定要注意这个。

对于子程序的性能，不要臆测，要知道只有Profile能告诉你真正的瓶颈所在。

第8章

在OI中，一般是完全不需要“防御式编程”的。我常常采用的方法是给需要传入的数据满足一定条件的函数处加上注释，而不是在程序中采取断言之类的措施。

第9章

在写程序前写高质量的伪代码的确是个提高代码质量的好主意，但在竞赛中还是把这个过程留在脑海中吧。不过以后有空的话可以考虑把所有常用的算法自己写一份伪代码，写完以后与CLRS之类的书上的伪代码进行比较。（其实也说不定自己写的才更好哦。）

第6章

加法原理的应用条件是分类后的集合是不相交的，但如果这个条件不满足呢？这就是容斥原理隆重登场的时候了。容斥原理是这样的A_1到A_n是对于需计数的集合分类后的集合，它们之间能有相交，总的元素个数就是|A_1∪A_2∪… ∪A_n| = ∑|A_i| - ∑|A_i∩A_j| + ∑|A_i∩A_j∩A_k| + …+ (-1)^m |A_1∩A_2∩…∩A_n|。它可以这样解释：首先加上所有集合的大小，然后减去每两个的集合并的大小，然后加上每三个集合的并的大小，然后减去每四个集合的并的大小，……，最后加或减所有集合的并的大小。它的证明可以通过计算某一元素对于等式每一项的贡献的方法来得到。

值得注意的是，如果和式中的每一项都需要直接计算的话，那么利用容斥原理的计算的复杂度关于n是指数级的。例如它用来计算一般的多重集的r-组合的个数就是如此。所以多重集的r-组合个数当元素的种数较多时似乎还是后面介绍的生成函数的方法更高效，它是伪多项式的。

错位排列（即元素i不在第i个位置上的排列）问题很有意思，它的特点是公式右边每一个和式里面的每一项是相同的，可以简化推导过程。最后的公式是：Dn = n! (1- 1/1! + 1/2! - … + (-1)^n 1/n!)。它有一个递推关系：D_n=(n-1)(D_(n-2) + D_(n-1)），可以组合推导。然后这个关系可以进一步简化为D_n = n D_(n-1) + (-1)^n，这个关系就不好组合推导了。

对于更一般的带有禁止位置的排列，就用一般的容斥原理就好了。

（墨比乌斯反演暂无）

第7章

算术序列就是等差数列，几何序列就是等比数列。顺便说一下，这里用a0（第0项）定义通项公式可比数学课本上用a1定义的公式优美多了。

求解递推关系是一门学问。比如说Fibonacci数的通项公式的样子很容易令第一次看到的人感到困惑。（八卦一下，我初中的时候曾经“证明”过 Fibonacci数不可能存在通项公式。呃……天才少年也有小的时候嘛……）现在的考试中似乎Fibonacci数的直接应用不多了。不过线性递推关系还是要看的。

一般的求解线性齐次递推关系的方法在此略过。

生成函数这个名字看上去有点神秘。但其实它就是将一个数列转化成一个函数的方法，定义函数的i次项的系数为a_i，就是数列a的生成函数了。将数列用这种方法表示出来可以方便处理和计算。比如说常数数列1,1,…的生成函数是1+x+x^2+……，但是利用无穷级数的求和，它同时可以表示成1/(1-x)这个很紧凑的形式，就方便接下来的处理了。

生成函数的首要用途是用来解元素的取法有限制的组合问题。比如说某元素只能取偶数个、某元素至多取b个最少取a个之类。对于每个元素的取法写成一个生成函数，就是如果能取i个x^i的系数就是1，否则为0。把所有元素的生成函数乘起来，得到的函数中x^i的系数就是取i个元素的方法数。

利用生成函数可以求解所有的常系数线性齐次递推关系。但目前还没有看到OI上的应用，所以在这里略过。

可以说，生成函数是一个模型，一个数学概念，就像“关系”“集合”这种数学上定义出来的东西一样。灵活的运用生成函数可以求解很多递推关系，比如Catalan数，还有后面讨论的很多数列。

指数生成函数是另一种生成函数。数列a的指数生成函数中x_i的系数是a_i / i!。常数列1,1,…的指数生成函数是Σx^i/i!=e^x。一般的，几何序列a_i=a^i的指数生成函数经化简是e^(ax)。它是用来解决和排列有关的问题的，典型的就是集合划分（更好理解的表达方式是涂色），例如某集合要被划分成若干个（有序的）集合，满足第一个集合的元素数是偶数，第二个集合不能少于a……这样就可以把每个集合的要求写成一个指数生成函数，然后分别化简以后乘起来就得到了通项公式。

可以看到，不管是常规生成函数还是指数生成函数，之所以用途很大就在于它可以被转化为很简单的形式方便运算（特别是乘法），还表达了原来数列的本质信息。

当vox.com被GFW的时候，我没有说话，因为我没有blog在VOX上。

当wordpress.com被GFW的时候，我没有说话，因为我也没有blog在Wordpress上。

当blogspot.com被GFW的时候，我也没有说话，尽管我在上面有一个blog，可我想反正可以通过pkblog访问它，由它去吧。

现在，我在上面安家的MyOpera也被GFW了……我终于想说些什么，可苦涩地发现我已什么也说不出来……

第5章

在OI这种极限运动中，与Design这东西有关的主要还是Algorithm Design，至于实现方面的Design由于代码量真的很小应该并不需要做，只需要按照惯常的风格和习惯去做就行了。所以说专业编程中的设计工作很险恶，但OI基本上还是在一个温室的环境里进行的。

设计的过程了无章法，就像在最终得出优美的正确算法之前会有很多稀奇古怪的东西出现。但“设计”就是为了犯错——让可能会在实现过程中出现的错误尽早地出现和被解决。这是一个启发式的过程。

软件的首要技术使命是管理复杂度(managing complexity)，这一点应该会让所有OIers颔首。但也许你首要想到的是时间/空间复杂度之类的东西。不过最先需要解决的问题是思维复杂度，它决定经你手写出程序的正确性。正确性，还有完整性（不能只写了一半），是比时空复杂度更先需要解决的问题。既然大脑不能把一个程序全部装进去，那么就需要把程序模块化，保证每个子程序的短小精悍和整体把握。设计的目标是易于理解，而不是smart。设计范畴内的每个特征都值得注意。

设计是分层次的，在某些OI程序里我们做到这一点可以减轻思维复杂度（尽管大多数不需要分层次的思维方式）。我们分出的模块（子系统）可能是：构图模块、网络流模块、二分答案模块，其中模块之间只有一条链型的依赖（也有可能是树形的，但一般还不会复杂到DAG）。在OI程序中使用类的情况不多，事实上我现在认为应该试图尽量减少，只有在不得不这样的情况下才去声明一个类（例如程序中用到了两个平衡树）；上面所说的类不包括没有成员函数的结构体。

设计有一些启发式方法。在OI中要抽象，必须要从题目的背景中跳脱出来。封装（一般指封装到函数）也是不错的注意，它让你看不到不必要的复杂度。信息隐藏、变化、松散耦合、设计模式等概念虽然异常重要，与OI关系却不大。其它的启发式方法中对OI可能有帮助的有：为测试而设计、考虑使用蛮力突破、画一个图、保持设计的模块化。109页改变自Polya的总结有点意思。至于剩下的过于具体（或者说高级？）的设计方法在OI中更是没有必要了。

最后提及的相关书目中的某些是将来（可能是较久的将来）一定要看的。

第6章

“在计算时代的早期，程序员基于语句思考编程问题。到了20世纪七八十年代，程序员开始基于子程序去思考编程。进入21世纪，程序员以类为基础思考编程问题。”

理解类首先要理解ADT，事实上在OI中用到的类一般都仅仅是ADT而已。

类的接口的设计是一门有意思的学问，但OIers暂时不需要研究这个。

包含是has a，继承是is a，老生常谈了。不过说实话在OI程序中这两种最常见的对象间的关系我好像都没用过。

在软件工程中创建类的原因很充分，但我现在倾向于认为在OI中可以尽量避免创建它，因为写起来麻烦一些，而且可能会给代码增加不必要的复杂度。比较充分的一个原因是在代码中会被复用（比如说需要用两个平衡树），还有就是建模。

第4章

本章讲了生成各种排列与组合的算法，最后提了一下偏序和等价关系的相关概念。

书中生成n个元素的所有全排列的算法并不好，原因是不按照字典序生成。其实我们需要的只是生成字典序意义下的“下一个”全排列的算法。设原序列为s[0..n-1]，算法是这样的：找到最大的i使s[i]<s[i+1]（若i不存在则不存在下一个全排列）；再找到最大的j使i<j、s[i]<s[j]，交换s[i]与s[j]；将s[i+1..n-1]的元素逆序。

排列的逆序列就是排列中每个元素逆序数构成的数列，一个元素的逆序数就是在排列中先于它且大于它的元素的个数。当排列中元素的取值一定时，根据逆序列可以构造出原来的排列。

生成集合所有子集（等价于0和1的n元组）的方法是类似于二进制进位的，也就是从01序列的一边开始不断把1改成0直到遇到一个0并把它改成1。还有一种方法是按照n阶反射Gray码的顺序生成这些n元组，不过似乎没什么用。

按照字典序生成前n个正整数的r-组合的算法看上去还是挺有用的，当然只需要研究如何生成“下一个”r-组合即可。舌原序列为s[0..r-1]，算法是：确定最大的k，使得s[k]+1<=n且s[k]+1未在s[0..k-1]中出现；将s[k..n-1]顺次设为s[k]+1、s[k]+1、…、s[k]+r-k+1。

（按照字典序生成r-排列的方法是什么呢？有待研究……）

定义一些关系R的性质：自反（对于所有x，满足xRx）、反自反（对于所有x，不满足xRx）、对称（对于所有x、y，若xRy，则yRx）、反对称（ 对于所有不相同的x、y，若xRy，则yRx不成立；或者说xRy且yRx仅当x=y）、传递（对于所有x、y、z，若xRy且yRz，则xRz）。

满足自反、反对称、传递的关系是偏序；将上面的自反改成反自反就成了严格偏序。对于偏序R，若任意x、y都有xRy或yRx，则R是全序。元素见存在偏序/全序关系的集合以及该关系称为偏序集/全序集。

有序偏序集的线性扩展（即所有元素的一个排列s[0..n-1]，若s[i]≤s[j]，则i<=j）跟拓扑排序是一样的。

满足自反、对称、传递的关系是等价关系。利用元素间的等价关系可以将集合划分成若干等价类；或者说，集合上的等价关系与集合的划分是对应的。

第5章

组合数C(n,k)出现在二项式定理中，所以它们也叫二项式系数。二项式系数有好多重要的性质。

Pascal公式：C(n,k) = C(n-1,k) + C(n-1,k-1)。当需要系统地求出一定范围内所有C(n,k)的值时，这是比较好的递推方法。证明方法是：从n个元素中选k个元素，可以选择元素1，这时只需从剩下n-1个元素中选择k-1个，方法数是C(n-1,k-1)，也可以不选元素1，这时的方法数是C(n-1,k)，根据加法原理可得结论。Pascal三角形是一个很有意思的图形，它的另一种解释是：从顶部开始，只能向下或下右走，到达点(n,k)的路径条数。

二项式定理：(x+y)ⁿ = C(n,0) xⁿy⁰ + C(n,1) x^n-1y¹ + … + C(n,k)x^n-ky^k + … + C(n,n)x⁰yⁿ。它的证明可以通过归纳法（代数方法）也可以通过二项展开式的组合意义得出。

二项式系数还存在另外一些恒等式：k C(n,k) = n C(n-1,k-1)；C(n,0) + C(n,2) + … = C(n,1) + C(n,3) + …；ΣkC(n,k) = n*2^n-1（1<=k<=n）；Σ C(n,k)^2 =C(2n,n)（0<=k<=n）；ΣC(r+i,i) = C(r+k+1,k)（0<=i<=k）；ΣC(i,k) = C(n+1,k+1)（0<=i<=n）……

k递增的二项式系数序列是单峰的，最大值为C(n,n/2)（如果n是奇数，那就有两个，分别是n/2取上整和下整）。证明可以由C(n,k) = C(n,k-1) * (n-k+1) / k的恒等式得出，这个恒等式可以用来求n一定的二项式系数序列，也可以用来求某个C(n,k)并最大限度减少溢出的可能性。

可以扩展组合数，定义C( n, (n_1,n_2,…,n_t))=n! / (n_1! n_2! … n_t!)，其中Σn_i = n。我们原来的C(n,r)在这种定义下表示为C(n, (r,n-r))。它表示把n个东西划分成t个集合，使第i个集合有n_i个物品的方法数。这也可以认为是所谓的多项式系数，有相应的Pascal公式、多项式定理，都很容易可以推广出来。

牛顿二项式定理是对前述二项式定理的推广。首先要推广组合数：定义C(a,k)=a(a-1)…(a-k+1)/k!（其中a是实数）。这定理就是：(x+y)^a=ΣC(a,k)x^ky^a-k（k=0..∞，也就是说，这是一个无穷级数）。在后面的生成函数部分这定理很有用，可以用来将很长的和式变成一个分式、根式或者相反。

偏序集的链与反链的性质很有用。链就是一个偏序集的一个子集，每两个元素都可比较，也就是说拓扑序唯一。反链就是偏序集每两个元素都不可比较的子集，或者说拓扑序任意。三个重要定理：偏序集中任一反链与任一链的公共元素不超过一个（这是明显的）；偏序集中反链的最大长度等于它能划分成链的最少个数；偏序集中链的最大长度等于它能划分成反链的最少个数（这两个优美的定理是对偶的，证明略繁，略过）。有了这些定理，就可以轻松地证明最小的上升子序列覆盖为何等于最长的不上升子序列长度了（若将偏序关系定义成i<j且s[i]<s[j]，那么LIS就是链）。

特别注明：这个算法是我昨晚神经抽筋想出来的，目前其正确性与时间复杂度没有经过任何验证。经过一定验证了已经，见最后。

设原字符串为S，长度为N。定义二维数组st[0..N-1][0..F]（st代表Sparse Table），其中F为N在二进制下的位数（F=[logN]+1）。st中任一元素的取值为[1,N]中的整数，且满足st[i][f]与st[j][f]的大小关系（小于、相等、大于）与S的子串S[i..i+2^f-1]和S[j..j+2^f-1]的大小关系一致。上述“子串”中的元素可能越界，故在算法中认为任何下标大于等于N的字符均为一个比任意字符都要小的字符（如’/0’）。在已知st[k][f-1]（0<=k<N）的所有值之后，子串S[i..i+2^f-1]与所有长度相同的子串的相对大小完全取决于st[i][f-1]⊕st[i+2^(f-1)][f-1]（⊕为连接运算），若i+2^(f-1)>=N，可简单地认为上述连接运算的右值为0，所以所有长度为2^f的子串可以利用基数排序的方法在O(n)的时间内排序，这个O(n)的排序基于的事实是：给定元素的两部分的取值均为[0,n]）。所以说可以利用O(n)时间求出st[k][f]。初始时st[k][0]的取值可以利用一遍计数排序求出，更简单地，可以令st[k][0]=S[k]（当S的长度小于字母表的大小时，这有可能违反st中元素取值为[1,N]的定义，但由于把字母表的大小看作常数，这样处理不会影响复杂度分析）。在求出st[k][F]（0<=k<N）的所有值之后，可以看出st[k][F]体现了S[k..N-1]在所有后缀中的（相对）位置，再经过一遍基数排序，就得出了后缀数组。O(nlogn)的时间复杂度是显而易见的。空间复杂度也为O(nlogn)，可以利用滚动数组优化成O(n)。另外，利用上述st表可以用O(1)时间回答S中任意两个子串的大小关系。

update: 使用USACO DEC06 GOLD 的 Patterns 一题测试，可以AC，这个算法的正确性应该没问题，效率嘛……反正比那个用hash做的标程要快许多。一共写了85行，其中求Suffix Array的核心部分大约40行。

示例程序：patterns.cpp

第一章

组合数学关心的问题是将一个集合的物体排列成满足一些制定规则的格式，一般的问题有：排列的存在性（是否存在两个正交的6阶拉丁方）、排列的计数和分类（m×n的棋盘上1×2骨牌的完美覆盖的个数是多少）、研究一个已知的排列（第一类Stirling数与第二类Stirling数的关系）、构造一个最优的排列（给出有向图中从S到T的最短路径）。

第二章

鸽巢原理，又叫抽屉原理。最基本的形式是：把n+1个物体放进n个盒子，至少有一个盒子包含不止一个物体。这个看似平凡的原理就可以用来证明很多有趣的结论了，比如说任意m个整数的序列肯定存在一个连续的子序列的和能被m整除。用它来证明结论最重要的是要巧妙地构造出“盒子”和“物品”，并且通过存在两个物品在同一盒子的事实得出某种结论。

个原理比较加强的形式是：令q_1，q_2，…，q_n为正整数，若将 q_1 + q_2 + … + q_n - n + 1 个物体放入n个盒子中，那么或者第1个盒子含有至少q_1个物体，或者第2个合资含有至少q_2个物体，……，或者第n个盒子含有至少q_n个物体。可以采用明显的反证法证明。这个加强形式可以用来证明长度为n^2-1的实数序列一顶包含长度为n的非增或非减子序列等一些更有趣的问题。

鸽巢定理的推广是Ramsey定理。Ramsey数r(m,n)是指：将完全图K_p的所有边任意涂成红色和蓝色，则或者存在红色的子图K_m，或者存在蓝色的子图K_n，r(m,n)就是p的最小取值。Ramsey定理就是在说对于任意m、n，r(m,n)都是存在的。虽然Ramsey定理说明了Ramsey数的存在性，但是对于Ramsey数的求法，目前还没有非平凡的结论，比如说r(3,10)、r(5,5)这些东西现在还没人知道它们的准确取值。

第三章

组合数学中出现最频繁的问题可以说就是对于某种有趣排列的计数了。目前为止一切的计数都依赖于两个原理：加法原理和乘法原理。前者指构成一排列共有两类不同的方法，第一类有a种，第二类有b种，那么构成这排列就有a+b种不同的方法；后者指构成一排列可以用两步来完成，第一步有a种方法，不论第一步选择何种方法第二步都有b种方法，那么构成这排列就有a×b种不同的方法。另外还有可以由它们推导出来的减法原理和除法原理，它们的使用可以使某些求解变得方便。

排列和组合是由基本技术原理导出的更高级的组合数学工具。

n个元素的集合中取出r个元素排成一排，共有P(n,r)种方法。P(n,r) = n × (n-1) × … × (n-r+1) = n! / (n-r)!。它的证明就是说这一排里的第一个元素可以从n个里面选，第二个可以从n-1个里面选，……，第n个可以从n-r+1个里面选，根据乘法原理可得。如果不是排成一排，而是排成一个圈，那么沿用刚才构造性的方法，每一个合法的方案出现了r次，根据除法原理，n个元素的循环r-排列的个数就是P(n,r)/r。

从n个元素的集合中取出一个大小为r的子集，共有C(n,r)个方法，C(n,r)就是组合数。C(n,r) = P(n,r) / r! = n! / ( r! (n-r)! )。可以通过利用乘法原理证明 C(n,r) × n! = P(n,r) 来得出这个公式。组合数这个东西可以构成很多恒等式，例如C(n,0)+C(n,1)+…+C(n,n)=2^n。这个恒等式可以通过“算两次”的方法证明，这种方法是利用组合方法（而非代数方法）证明恒等式最常用的途径。

在排列问题中，如果每个元素都可以被取无数次，或者说待取元素的集合中是一个多重集，其中每一个都出现无数次。那么方法数就是r^n。如果多重集的k个元素中第i个元素出现n_i次（Σn_i = n），那么排列总数就是n! / ( n_1! × n_2! × … × n_k )。

若多重集元素的重复数是无限的，那么具有k个元素的多重集的r-组合总数为 C(r+k-1,r) = C(r+k-1,k-1)。这可以通过转化成求方程 x_1 + x_2 + … + x_k = r 的非负整数解的个数来得出，求解过程需要先做一个代换y_i=x_i+1，这样y_i就是正整数，类似的每个变量有下界的不定方程的整数解的个数都可以通过类似的代换解决。

第1章

构建（Construction）的确是软件工程中最主要的环节。特别的，在我们的信息学竞赛这一规模很小的“工程”中，Design和Testing可探讨的空间不大不大。Design过程中出错几乎无药可救，Testing一般不会出什么错；或者说，OI中的Design和Testing不属于“工程”的范畴，可称作工程的只有Construction，也就是Programming。

第2章

在隐喻的层面，软件业界中已经广泛地认识到了增量开发的重要性，而信息学竞赛的语境中还使用着一套相当落后的隐喻（写信？），甚至有很多人从来没用过什么软件工程意义上的隐喻。应该把写程序看成一个“培育”的过程，一点一点做，最终长出珍珠；建造/修饰的隐喻体系也不错。这两个隐喻体系和分点测试的OI在精神层面上是暗合的。

在中国的比赛的环境中，“买得到的东西”比较少，但正因为如此，我们应该更娴熟地掌握和运用它们。比如说，我已经很长时间以来都没有写过qsort了。

规划得当的项目具有“在后期改变细节设计”的能力。我们书写的代码也应当如此。比如说，把我的网络流程序的存储方式由邻接表改成邻接矩阵（或者相反），我可以保证一切需要改变的不超过5行代码。这需要一种成熟和良好的书写模式/习惯。

总的来说，隐喻这种东西对于OI来说，在软件工程的层面的启示并不大，我们使用更多的是利用隐喻来理解算法。最简单的，其实“Queue”或者“Tree”都是隐喻。

第3章

OI中，构建前的前期准备让人困惑。似乎就是想出来算法吧。但是，你真的“想出来”算法了吗？或者说……你真的准备好了吗？在写程序之前，和写程序之后，把思路在脑海中理顺一遍似乎是个好主意。

按照正确的顺序做事情，这很重要，在上一章或上上一章也提过。先把圣诞树立起来，再对它作装饰。或者说，先写好DFS的框架，再去剪枝。（注意这也只是一个类比而已。）熟练的OIer写出的DFS框架应该是很容易嵌入剪枝代码的。

发现错误的时间要尽可能接近引入错误的时间。因为修复错误的代价是随着错误诞生的时间呈指数式增长的。我不确定这是否意味着我们应该在写完每一个函数之后先看一遍再开始写下面的东西，因为看上去太浪费时间。也许做到这一点最好的办法还是尽量的增量开发吧。

选择序列式开发法和迭代式开发法各有不同的理由，他们适用范围就不同。但我认为仅仅一个理由就可以让OI采用迭代式开发法（在这个语境下“增量式”似乎是更好的描述？）：分点测试。

“需求”的概念在软件开发中性命攸关，但在OI中似乎真的没有它的位置。“架构”这种东西似乎也一样。

OI中，解决一道题有多少时间需要花费在前期准备上？似乎是因题而异的。唯一可以确定的大约有两点：如果你发现看完题后一秒钟就可以开始写代码了了，那么最好再看一遍；如果这道题的“前期准备”花了10min（或者一个更为妥帖的时间限制）屏幕上还没有一行像样的代码，那么暂时放弃。

第4章

编程语言的选择对软件项目影响巨大，这是经过严格的研究证实的，它甚至影响程序员面对问题时的思维。想必OI中也是这样，比如说你可以看到USACO月赛中从Bronze到Silver至Gold的组别中C/C++对Pascal的比率严格递增。或者说，NOI中使用C/C++的选手比例肯定会比NOIp中高。这也许是互为因果的。

编程约定是一个有用的东西。在我的程序中，它会以变量或函数处的一行注释体现。——变量的意义，表示特殊意义的值（例如-1表示还未计算），调用的先决条件，等等。它们是在实现前写的，而何时需要它们则是一个相当经验性的东西。