前几天在写HDU6619的时候，问题最终转化成了一个形如下式的DP：

$$dp[i] = \left\{ \begin{aligned} &x &i = 0 \\ &max_{0\leq j < i}\{dp[j] + (n - i)(\Sigma_{k = j}^{i - 1}arr[k])\} &0 < i \leq n \end{aligned} \right. \\$$

这个式子很简单，也就是当前状态的值由前面某个状态的值加上两个状态之间的数组值的和得到，且当前状态的值要尽可能大。按照式子直接枚举当前状态的上一状态的话，复杂度是$O(n^2)$。但本题的$n$是$10^5$，直接写肯定会T掉。我一时半会没有想出优化的方法，看了题解才想起来，这个DP可以用斜率优化来加速转移。于是，我准备快速复习一下斜率优化的用法。

斜率优化DP用法示例

还是回到刚刚那个式子:

$$dp[i] = \left\{ \begin{aligned} &x &i = 0 \\ &max_{0\leq j < i}\{dp[j] + (n - i)(\Sigma_{k = j}^{i - 1}arr[k])\} &i>0 \end{aligned} \right. \\$$

右边一堆求和实在是太碍眼了。我们可以先对数组求前缀和，这样求和直接被前缀和做差代替：

$$dp[i] = \left\{ \begin{aligned} &x &i = 0 \\ &max_{0\leq j < i}\{dp[j] + (n - i)(sum[i] - sum[j])\} &i>0 \end{aligned} \right. \\$$

如果没有那个$(n - i)$就好了。这样上一状态的贡献永远是$dp[j] + sum[j]$，只要对每个状态求这个值再取最大就可以直接$O(1)$获取之前答案的最大贡献了。问题是，前面乘了一个$(n - i)$后，之前状态的贡献就和当前的$i$有关系了。之前所有状态的部分贡献$dp[j],sum[j]$已经是完全确定的东西了，加上当前的$i$就能算出之前状态的全部贡献。那么，有没有一个仅通过当前的$i$来衡量之前哪个方案更优的方法呢？

如果之前存在两个状态$a,b$，不妨设$a < b$。那么，当从$a$比从$b$转移更优的时候是怎么样的呢？我们不妨列出此时两个状态的贡献值不等式，并且把含$i$的部分移到不等号的一边去。

$$\begin{aligned} dp[a] + (n - i)(sum[i] - sum[a]) &> dp[b] + (n - i)(sum[i] - sum[b]) \\ dp[a] - (n - i)sum[a] &> dp[b] - (n - i)sum[b] \\ dp[a] - dp[b] &> (n - i)(sum[a] - sum[b]) \\ \frac{dp[a] - dp[b]}{sum[a] - sum[b]} &> n - i \end{aligned}$$

由于前缀和数组递增，$sum[a] > sum[b]$，不等式不用变号。

也就是说，通过计算两个状态的$dp$数组差除以$sum$数组差，并将这个结果与$n - i$比较，我们就能知道之前两个状态孰优孰劣。这个计算出的值是反映状态好坏的本质属性，因为这个值的计算与当前的$i$无关。由于这个计算值和数学上斜率的计算十分相似，因此才有斜率优化这个名字。

如果把之前所有状态都看成一个$(sum[j], dp[j])$的二维点，现在我们知道了$n - i$的值，那么之前哪个状态最优呢？

我们从左到右从两两相邻的点连线。如果两两相邻的点的斜率是递减的，那就好办了：这就说明，前面有很多点对的斜率大于$n - i$，后面有很多点对的斜率小于$n - i$。那么中间的某个点就是最优的，那个点和它前一个点的斜率大于$n - i$，和它下一个点的斜率小于$n - i$。它比左边的点优，也比右边的点优。

问题是，如果出现了某三个从左到右相邻点$a, b, c$，且$ab$斜率小于$bc$呢？也就是相邻点对的斜率不是增减的。这种情况下，若斜率$ab$和$bc$都比$n - i$小，则最左边的$a$点最优；反之，若两个斜率都比$n - i$大，则最右边的点$c$最优。剩下的情况只有斜率$ab$小于$n - i$，斜率$bc$大于$n - i$这种情况。但是，此时$a$比$b$优，$c$也比$b$优。可以看到，无论什么情况下，$b$都不是最优的。因此，$b$点永远不会是上一个最优状态，可以把它“抛走”，再也不考虑它了。

也就是说，可能作为上一个最优状态的点，它们的$(sum[j], dp[j])$构成的二维点的斜率永远是单调递减的。这个单调性，是斜率优化DP的根本原因。

有了上述的分析，选上一个最优状态，不再需要枚举每一个之前的状态，而是维护一个可能作为上一状态的集合就可以了。这个集合从左到右存了一系列的可能的状态。每次要找最优状态的话，就像之前分析的那样，找到第一个斜率小于的$n - i$的左边的点，那个点对应状态就是最优的上一状态。由于单调性的存在，这个过程可以用二分完成。但由于我们每次的$n - i$是一个递减的量，也就是说我们每次需要找的斜率只会越来越小。那么那些斜率很大的点都可以扔掉去。因此，在本题中，可以不去二分查找，而去删掉前面那些已经斜率过大的点。最后剩下来的第一个点，它和下一个点的斜率小于$n - i$，它就是本次要寻找的最优上一状态。这个集合可以用双端队列Deque来维护。

同时，这个集合还需要进行维护。每次新得到了一个dp值后，我们就要试图把新的状态加入这个集合中。为了保证集合中点斜率的单调性，我们要取出集合最后两个点，拿它们和当前的点算出两个斜率，看看这个斜率是否满足单调递减的性质。如果不满足，就把中间的那个点去掉，也就是把原来集合中的最后一个点去掉。

Deque实现斜率优化DP方法简述

其实上面那道题并不适合用来学习斜率DP，因为它实际上牵扯的细节很多，dp式子并没有上面写得那么简单。HDU3507应该是最适合写的第一道斜率优化DP题。

这道题状态转移的式子比上面那个例子要复杂一点，而且是取最小值，需要维护的斜率应该满足单调递增而不是单调递减，但本质还是对前缀和什么的做一些运算，再进行斜率的比较，最终优化的方法还是完全一样的。

这道题中，不等式右边的与当前状态$i$有关的值是$sum[i]$，它是一个单调递增的量，正好与我们维护的是一个单调递增的斜率集合“相符合”（这里“符合”的意义比较微妙，也就是说，如果这里$sum[i]$不是单调递减，是递增或是无规律的，那么就不能用Deque来做了）。因此，我们在找最优状态的时候，不用去二分的找第一个斜率大于某个值的点，而是把前面斜率小的点都删掉去，把剩下来的第一个点作为上一状态。这个东西可以用Deque维护。

因此，在写代码时，应该按照下列步骤。

1. 读入数据，初始化dp等数组，该求前缀和求前缀和。
2. 声明一个deque\< int >，作为上一状态的集合。如果0位置的状态一开始就能被转移，就往deque里push一个0。
3. 开始for循环，遍历每一个当前状态$i$。
4. for循环体中：如果deque的大小大于等于2，说明deque中可能存在斜率不合法的点，循环寻找是否存在这样的点。每次循环得到front()，再pop_front()，再得到front()，也就是取出队列中前面两个点。判断这这两点的斜率，若斜率小于（大于）关键值（本例是2 * sum[i]），则continue掉，也就是扔掉第一个点，继续循环判断；否则，把取出的第一个点push_front()放回去，退出循环。这样，第一个斜率大于（小于）关键值的点就变成了que.front()。
5. 不妨设j = que.front()，这个j就是最优的上一状态。用推好的dp式子计算dp[i]。
6. 把状态i加入队列并维护队列的单调性。和开始的操作类似，循环判断deque大小是否大于等于2，若是，则取出队列队尾的两个点，计算它们和新的点$i$的两个斜率是否满足应该具有的单调性。若不满足单调性，则扔掉队尾的点，循环继续。
7. 把状态i用push_back()扔进队列的队尾。
8. for循环结束
9. 输出dp数组中的答案。

二分查找实现斜率优化DP方法简述

CodeForces 674C也是一道斜率优化DP的题目。这道题递推式子相较之前两题更复杂了一些，而且它进行比较的和$i$有关的关键值并不是单调的。因此，这题不能再用Deque来维护最优上一答案，而是要用一个vector来存可能的状态，并进行二分查找。

写代码的步骤也类似，只是寻找上一最优答案的过程有所变更。

1. 读入数据，初始化dp等数组，求好所需变量。
2. 声明一些vector\< int >，作为上一状态的集合。如果dp某一维的0位置的状态一开始就能被转移，就往对应vector里push一个0。
3. 开始for循环，遍历每一个当前状态$i$。如果dp数组和本题一样是多维的，那么再加一层for循环，按照顺序遍历dp数组的每一维。
4. for循环体中：如果对应vector数组是空的，那么说明该状态不存在上一状态，直接跳过；否则，声明一个存储最优上一个状态的变量ii。ii的初始值是vector数组的第一项，因为我们将要二分查找的是最后一个斜率满足不等式的右端点，若二分查找什么都没找到，那么说明最优的点就是数组中的第一项。
5. 二分查找最后一个斜率满足不等式的右端点。实现时把二分查找的mid对应状态套入不等式判断即可，若满足不等式则更新临时变量ii为vector中mid处对应的状态。
6. 二分查找结束，ii就是最优的上一状态。用推好的dp式子计算dp[i]。
7. 把状态i加入数组并维护数组的单调性。循环判断deque大小是否大于等于2，若是，则取出数组尾的两个点，计算它们和新的点$i$的两个斜率是否满足应该具有的单调性。若不满足单调性，则扔掉数组尾的点，循环继续。
8. 把状态i用push_back()扔进数组尾。
9. for循环结束
10. 输出dp数组中的答案。

写代码的注意事项

写代码的时候会发现，不等式左边分子的那个量会被反复地用到。用一个函数来计算这个值会更加方便可靠。

在比较相邻两个斜率，而分子分母都是整数的时候，得用交叉相乘来比较斜率，规避除法。

总结/感想

算法原理

我算是大概理解了斜率优化DP的原理，但对什么时候可以用这个算法还有一点模糊。斜率优化DP本质上是在寻找最优上一状态时，找到衡量每一个状态的本质量，也就是那个二维点。对于每一对二维点，都有同一个判断它们两个谁更优的标准，那就是比较二者斜率是大于还是小于某个值（等于的情况可以忽略）。由于判断条件相同，只有斜率单调的点才可能成为最优上一状态。又由于有了单调的性质，才能在状态中进行二分查找。如果进行判断的斜率值还相对应是单调的，那么二分查找都可以省略，直接就可以得到最优的上一个状态。

能用斜率DP优化问题的核心原因就在于，对每一对二维点，判断它们谁更优的标准是一样的。但是，如果对于一个dp递推式子推导出的不等式中，作为分母的不是$(sum[a] - sum[b])$，而是另一组值，这一组值并不满足单调。这样的话，哪怕对于$a > b$的点，算出来的分母可能是个负数，除过去的话不等式要变号。对于相邻的两个点，有的时候斜率大于某个值更优，有的时候是斜率小于某个值更优。好像在这种情况下就不能用斜率优化DP了。

算法适用情况

能够用斜率优化DP的题都有类似的地方。这些题的dp在计算新值时，是在旧dp值的基础上加上一个和当前状态$i$有关的贡献。这个贡献往往是和上一位置到这一位置的区间和有关，以保证不等式分母是永远是正的。当看到一个类似这样的DP，且数据范围不允许$O(n^2)$时，就要考虑用斜率优化DP了。

和大部分DP题目一样，这种题目推式子是最重要的，代码实现上只要写个2、3题就能学会套路，很难出错。

我之所以开通博客，是因为我感觉自己有很多想法，想把它们整理、发表出来。但在我开通了博客之后，我写的文章却非常少。我仔细分析了一下自己的心理，发现我并不是没有东西可写；相反，我经常会想到一些想写的话题。但是，当我准备去构思文章该怎么写的时候，我总不自觉地会开始想一些问题：“我要写的东西会不会太短内容不够？”“我写的东西会不会内容涉及得不够全面？”“我不去查阅资料就来写会不会失去严谨性甚至是正确性？”想的问题多了起来后，我就会发现自己还没有做好写这篇文章的准备。于是乎，一篇文章就这么搁置下来了。

再仔细一想，我这种有想法却没写出来的现象是有原因的。原因分客观原因和我自己的主观原因。

先来控诉一下这个世界的不公。文章的质量的越高，所需要的投入也越高。正如我想的那些问题那样，一篇高质量的文章，需要先对所谈的话题进行信息的收集，保证全面性、严谨性；再把自己之前的思考同收集的信息整合起来，整理总结自己的思想，确定表述的内容；最后确定好文章的结构，按照合理的顺序，用文字把想法表达出来。文章的质量越高，花费的精力肯定就越多。但是，写一篇好文章，对我来说没有任何利益上的回报。不管我再怎么欣赏自己的才华，再怎么愿意给未来的自己多留一份回忆，也掩盖不了我的内心对于做一件没有收益的事情的抵制。投入和回报不成比例，我写高质量的文章注定会缺乏动力。要不是实在是时间有多，精力有剩，我是无法具备足够的动力的。因此，从客观上来看，对我来说，一直写质量较高的文章是不可能的。

现在可以谈我自己的问题了。我为什么非得要写那么好的文章呢？想到什么就说什么不行吗？非得把博客当成高考作文来写？我开始分析起了自己的心理。我也有想过快速完成一些短一点的文章，但我一想到这些文章可能会写得不够好，像程序一样充满“BUG”，心里就很不是滋味。我想的事情并不是写出好的文章，而是不希望文章中有漏洞，有缺点。我把写文章当成了一种自我展示、自我实现的工具。文章中有纰漏，文章写得不好，就会显得我这个人有缺点。为了让我自己显得更完美，我把这种对于完美的追求代入了文章中。我希望用一篇质量高的文章，来反映一个能力强的自己。我产生这些想法的原因和其他很多表现都是一样的。有些人在乎穿着打扮，认为外貌能反映自己；有些人在乎言行，以自谦来衬托自己的高尚。我虽然不在意别人的看法，但我也在用我写的文章，或者我的一些其他成果，来作为自己好与差的评判标准。对于事物的缺点的掩饰，不过是出于自卑，出于对自己的不足的掩饰罢了。

显然，客观的原因不可改变。除非有人说：“你写的文章太好了，让我五体投地，感慨万分。从今天起，你也不用干其他事了。你写一篇好的文章，我就给你十万块钱。”不然的话，缺乏客观上的利益，我没有足够的动力去写东西的。

但是，我还是有很多东西要表达出来，我得实现我开通博客的初衷。那么，我只能设法改变自己的想法了。我的问题就在于，过分追求完美。

说来也有点讽刺。我对于过分追求完美这个问题，也有过很多思考，也有把这些想法整理出来的打算，但也因为上述种种顾虑迟迟动不了笔。我今天只能说对完美主义进行一个简单的分析，并把如何改变自己而不是探讨理论作为文章的重点。

完美主义的具体定义我是不知道。但很明显，我上述的表现，都是完美主义的常见表现：想把事情做到最好，却最后什么也没有做。

从本质来看，完美主义是不成立的，因为人本身就不是完美的。人的精力有限，人的能力有限，人注定不可能把每件事做到极致。而完美主义所追求的”完美“，不是事物质量的完美，而是能否通过事情的完美展示人自己的“完美”。由于人的限制，这种完美主义注定会失败。

完美主义，错就错在动机。人生来自卑，人想尽可能让自己变得更好，或者说仅仅是看上去很好，这种希望本身没有错。但是，把事情做得很好，做得“最好”，并不等价于你这个人就是“最好”。这两者没有任何关系。甚至反过来，不去急功近利地追求成果，而是潜心雕琢，反而能达到结果的完美。一个的人价值，不能被任何外在的事物所体现，所代表。认识到了完美主义出错的那个关键点，纠正事物完美等于自我完美这个想法，就能克服这种完美主义了。

现在谈回我自己。既然我对自己的想法、自己的问题都深入思考到这个程度了，我以后该做出哪些改变呢？写长的文章没有动力，我就写一些短的文章啊！文章短又如何？质量差一点又如何？只有让写一篇的文章的成本低到一定程度，直到低于我写文章的回报，我自然就有动力去写了。

那又回到我第一篇博客谈的问题了。我为什么要写博客？我能得到什么回报呢？我也不放眼未来，把这个问题展开来谈。我就谈一下近期我写博客能获得的回报。如果是写一篇介绍算法的博客，我能利用写博客这个机会，去把一个算法彻底学会。写的文章好不好，有没有人看，都和我的收益毫不相关。如果是写一篇像这篇文章一样，吐诉内心想法的文章，那就想到什么写什么，管他写的是什么东西，写得自己爽就好了。如果我想把我的想法一些整理出来，给别人看，认同我提出的观点，那我就得提升文章质量，增强说服力，让他人被我的文笔和人格魅力所折服。如果我写的是题解，那么我只能稍微提升一下对于题目的理解，并且略微提升一下我本来就很强大的语言组织能力，再期待这篇题解能被别人看到，增加自己的知名度，收益就不高了。如果我复习时没有动力，我就像上学期那样，通过写博客来敦促自己系统地复习知识。如果我吃饱了没事，想吹吹牛展示一下自己，就可以针对某项成果单独开一篇博客来吹嘘一番。

这样一看，不同类型的博客，收益的种类也是不同的。我之前只是把博客当成一种证明自己完美的手段，而忽略了写博客还有如此多其他方面的收益。只要我能把写博客的成本降低，我自然而然地就能获得写博客的收益，就像这篇文章一样。我需要去掉的成本，就是那些名字好听，被称为“完美”的成本。

题目按个人感受的难度升序排列。

J Fraction Comparision

Description

给$\frac{x}{a},\frac{y}{b},0\leq a,b\leq 10^9,0\leq x,y\leq 10^{18}$，问这两个分数比较大小的结果（大于、小于或等于）。

Solution

由于浮点数会有误差，不能除了以后再判断。

用有大整数的语言的话，可以直接通分比较。

用C++的话，可以把两个分数划为带分数。比较带分数时先比较整数部分，再通分比较真分数部分。由于分母在1e9范围内，不会爆long long。

F Random Point in Triangle

Description

给平面上一个三角形，顶点为ABC。现在随机再三角形内部取一点S，S把三角形划分为三个小三角形。问这三个小三角形面积的最大值的期望乘36（保证这样算出来的结果是整数）。

Solution

我在知乎上看到过类似的题目，原理没记住，结论倒记住了：这种三角形随机取点求面积期望的题，与三角形形状无关，只与面积有关。原理好像是坐标变换什么的，不管三角形形状是怎么样的，都可以通过坐标变换变成同一个三角形。这个坐标变换的过程面积也是按照比例变化的。大概是这个意思，我也说不清楚具体的原理。

有了这个结论，只需要知道面积为1的三角形的答案就行了，这个直接在本地模拟就行。我把三点设为(0, 0), (0, 1), (1, 0)，取两个随机数后把随机数都映射到[0, 1]中，再判断这个点是否在三角形内。如果这个点在三角形内，就用叉积算三个小三角形面积。不断地大量随机取点后再除一下有效点数量就是答案。

判断点是否在三角形内可以考虑判断三个小三角形的面积是否“正负号相同”（即叉积结果符号是否相同）。

最后发现面积乘22就是答案,也就是叉积的结果乘11。

B Integration

Description

已知$\int_{0}^{\infty}\frac{1}{1+x^2}dx=\frac{\pi}{2}$，
给定$a_1, a_2…a_n(1\leq n\leq 10^3，1\leq a_i\leq 10^9,a_i互不相同)$，求$\frac{1}{\pi}\frac{1}{\Sigma_{i = 1}^{n}(a_i^2+x^2)}dx$模$10^9+7$意义下的值。

Solution

这道题只需要微积分的基础知识，即积分的线性性质：积分里面如果是相加的话可以拆开来积分再相加。但题目里面的积分是相乘，只能考虑把积分内的乘积化为简单的分式相加，再套入题目给的公式了。

分式的乘拆分成分式的和则是初等数学的内容了。不妨先考虑$n=2$的情况，考虑$\frac{1}{(a^2+x^2)(b^2+x^2)}$的拆分结果。

设$\frac{1}{(a^2+x^2)(b^2+x^2)} = \frac{n}{a^2 + x^2} + \frac{m}{b^2+x^2}$，则：

$$\begin{aligned} \frac{1}{(a^2+x^2)(b^2+x^2)} &= \frac{n}{a^2 + x^2} + \frac{m}{b^2+x^2} \\ \frac{n}{a^2 + x^2} + \frac{m}{b^2+x^2} &= \frac{b^2n+x^2n+a^2m+x^2m}{(a^2+x^2)(b^2+x^2)} \\ 1 &= b^2n+x^2n+a^2m+x^2m \\ 1 &= b^2n+a^2m+x^2(m+n) \end{aligned}$$

由于上式恒成立，可得：

$$\left\{ \begin{aligned} b^2n+a^2m = 1 \\ m+n = 0 \end{aligned} \right.$$

解得：

$$\left\{ \begin{aligned} n = \frac{1}{b^2 - a^2} \\ m = \frac{1}{a^2 - b^2} \end{aligned} \right.$$

用同样的方法可以求得n为任意值时的拆分结果。对于分母是$a_i^2+x^2$的项，它的分子是$\frac{1}{\Sigma_{j\neq i}(a_j^2-a_i^2)}$。

再由微积分的知识，$\int_{0}^{\infty}\frac{C}{a^2+x^2}dx=\frac{C}{a^2}\int_{0}^{\infty}\frac{1}{1+(x/a)^2}dx =\frac{C}{a}\int_{0}^{\infty}\frac{1}{1+(x/a)^2}d(x/a) =\frac{C\pi}{2a}$，

因此，对于分母是$a_i^2+x^2$的项，积分的结果是$\frac{\pi}{2a_i\Sigma_{j\neq i}(a_j^2-a_i^2)}$。算出了公式，转换成程序就行了。

C Euclidean Distance

Description

给一个n维空间的点$A(a_1/m, a_2/m…a_n/m)$，求它到点$P(p_1, p_2, …p_n)$的最短距离的平方，即$\Sigma_{i = 1}^{n}(a_i/m - p_i)^2$。其中点$P$要满足下列条件：
$p_i\in \Reals$
$p_i \geq 0$
$\Sigma p_i = 1$

答案用分数的形式表示。

数据范围：
$1 \leq n \leq 10^4,1\leq m \leq 10^3, -m\leq a_i \leq m$

Solution

为了方便说明，先把点$P$的每个坐标分量乘一个m，我们要求的东西变成了$\Sigma_{i = 1}^{n}(a_i - p_im)^2$。只要把这个结果除以一个$m^2$就是题目的答案。

由于点$P$的分量都大于等于0，且和为$m$，我们可以考虑把点$P$的坐标看成是实数$m$“分配”到每一个坐标分量$p_i$上。即我们可以让每一个$p_i$变大一点。

我们如何让距离尽可能短呢？如果在某一维上，比如第$i$维，若$a_i < 0$，那么此时令$p_i$增长的话，那么距离只会越来越长；如果$a_i > 0$，那么$p_i$越靠近$a_i$，那么最终的距离就会越短。当$p_i = a_i$时，我们就不用让$p_i$增长了。

由不等式$a^2+b^2\geq2ab(仅当a=b时等号成立)$我们发现，数越大，其平方也增长得越快。如果此时我们去缩小一个本身就很大的数，就能让平方和减少得更多。具体来说，对于两个点的第$i, j$两个维的坐标分量,若$|a_i-p_i|>|a_j-p_j|$，那么让$a_i,p_i$更接近一点，比让$a_j,p_j$更接近一点，更能让总距离减小。那么在分配$m$到$P$的每一维时，应该先分配给$a_i$最大的地方，缩小此处$a_i和p_i$的差距。等这一维的距离和$a_i$中第二大的数时，就要同时缩小这两个维上的距离了。

比如$A(2,3)，m = 3$，我们发现$a_2 > a_1$，于是先从$m$中分配$1$给$p_2$，此时$P(0,1)$，$|a_2 - p_2| = |a_1 - p_1|$。我们再让这两个距离同步减小，从$m$再分配1分别给$p_1,p_2$，此时$m=0$,分配结束，而$P(1,2)$，$|a_2 - p_2| = |a_1 - p_1|$依然成立。这种情况下得到的$A,P$两点的距离是最短的。

有了上述思想，算法也就呼之欲出了。把所有$a_i$降序排序，按照上述方法分配$m$的值，尽可能让最大的几个距离相等，再同步减少这几个最大的距离。这种分配方式对于$a_i$是负数的情况也是成立的，不用多加考虑。注意一下有理数分子分母的处理方式即可。

Review

有时对于一道看上去复杂的数学题目，用一些比较简单的、定性的方法就能解出来。

A Equivalent Prefixes

Description

在两个数组$a, b$的前$m$项上，定义一个等价关系：若两个数组前$m$项任意一个区间$l,r$的最小数的位置相同，则称两个数组前$m$项等价。现在给两个数组$a,b$，问它们最多前几项是等价的？

数组长度为$n$

数据范围：
$1 \leq n \leq 10^5$
$1 \leq a_i,b_i \leq n, 所有a_i,所有b_i互异$

Solution

这个等价关系的意思好像就是说，每个数作为最小值的影响范围相同，即每个数碰到的左边、右边第一个比它小的数的位置都相同。这个东西好像就是笛卡尔树啊！

二分答案，对前$mid$项构建笛卡尔树，若笛卡尔树完全相同就check成功。

Review

从知识和写代码的复杂性来看，这道题肯定不是难度第二低的题目。但是，从全场的通过情况来看，这是大部分队第二道通过的题，也是通过人数第二多的题。

可以得出结论：很多题目，不是难到不会写，而是难到不敢写；有本来比较简单的题目没来得及写，不是你没有AC，而是别人没有AC。

话说笛卡尔树的定义和用途其实我现在都没有弄清，但我知道这个东西用单调栈就可以构造，而且所涉及的所有知识都建立在单调栈方面的知识上。

E ABBA

Description

给定$n,m$，问有多少个长为$2(n+m)$的字符串，’A’和’B’各$(n+m)$个，使得该字符串能够被拆成$(n+m)$个长度为2的子序列，其中有$n$个子序列是”AB”，$m$个子序列是”BA”。

数据范围：
$0 \leq n,m \leq 10^3$

Solution

本题最大的障碍在于，题目对于n个AB子序列和m个BA子序列的限制条件，等价于说：对于任意的$i$，字符串前$i$中不能出现A比B多$n$个以上的情况，也不能出现A比B少$m$个以上的情况。证明如下：

充分性：
即证逆否命题：如果字符串中出现了A比B多$n$个以上的情况，则不能满足题目的条件。假设在某个位置，A比B多$n+1$个，则前面这些多出来的$n+1$个A永远不能放在B的后面，也就是最多只有剩下的$(m+n)-(n+1)=m-1$个A能够构成BA，但是$m-1$个BA是不能满足题目的限制条件的。

不能有A比B少$m$个以上的情况的证明类似的。

必要性：
即证满足AB的数量条件即能满足题目的限制条件。考虑构造出题目中要求的$(n+m)$个子序列。从左到右读一个满足AB数量条件的栈，用一个栈来构造这些序列。首先，构造$n$个AB。像括号匹配一样，A当成左括号，B当成右括号。一旦栈中出现了AB，就弹出AB并且令AB子序列数+1，直到构造完$n$个AB。由于在任何时刻不会出现A比B少$m$个的情况，栈中最多有$m$个B，剩下的B全部可以构造成AB。所以这个$n$个AB一定可以构造出来。

栈中可能会剩下很多B，B后面又跟了很多A。而现在我们要构造出$m$个BA。先把栈中已经配对成功的BA弹出，直到栈中全部是A或者全部是B为止。继续从左向右读字符串，如果当前栈顶是B，又读入一个A，则弹出这个BA；若当前栈顶是A，又读入了一个B，则从前面我们构造好的$n$个AB中随便挑一个出来，则之前的AB和现在栈顶的两个AB构成的子序列是ABAB，注意到这个子序列可以拆成A(BA)B，因此我们依然可以构造出一个BA来。后面这种替换是有限度的，如果连续的A碰到了连续的B，则需要之前有足够的AB才行。比如栈里面现在是AAAA，下面4个字符是BBBB，则需要连续替换4次。为了保证替换成功，前面一定要有4个AB才行。但我们现在有前提条件，不存在A比B多$n$个以上的情况，即栈中不可能有$n$个以上的A，也就是说连续替换的次数一定小于等于$n$。而我们已经构造出了$n$个AB，这种替换的一定可行的。

综上，按照上述方法，我们可以构造出题目要求的$(n+m)$个子序列。

有了上面的证明，题目的要求就变成我们自己的等价描述。那么只需要一个dp数组来统计方案就行了。$dp[i][j]$表示长度为$i$的字符串，A的个数减B的个数等于j的方案数。这个dp十分巧妙，dp的范围自动删除掉了A与B数量不符合要求的字符串。那么转移方程为：

$$dp[i][j]= \left\{ \begin{aligned} &1 &i = 0\bigwedge j = 0 \\ &dp[i - 1][j - 1] + dp[i - 1][j + 1] &i\geq 1 \bigwedge -m \leq j \leq n \\ &0 &else \end{aligned} \right.$$

$dp[n][0]$就是题目的答案。数组下标不能是负数，稍微处理一下就好了。

Review

很久没打比赛，我的思维现在非常死板。我想这道题的时候误入歧途，一直想用排列组合算这道题。明明我在暴力枚举验证我猜的结论的时候，已经用到了栈来判定字符串是否合法了，但我还是没有想到只要保证A与B之间的数量关系就行了。

当我看到这个结论的时候，觉得这个结论十分简单。但证明起来却发现，充分性很容易想到，必要性的构造却是要花一番功夫才能证明出来的。比赛中我们往往想到了某个结论的充分性，就会匆匆忙忙地猜结论。这样有时候或许侥幸能过题，但一旦过不了就会很伤士气。我平时就要养成严格证明的习惯，并且同时加快证明的速度，对于一个想到的结论要简单地从两个方面证明等价，不要想到一个结论就立刻跃跃欲试，脑袋都空掉了。

H XOR

Description

给$n$个数$a_1, a_2…,a_n$构成的集合，从该集合找出子集，这些子集的异或和为0，求这些子集的集合大小之和。

答案模$1e9+7$

数据范围：
$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^18$

Solution

首先，求出所有的集合并统计它们的大小是十分困难的。但所有集合的大小和，等于分别讨论每个元素的贡献，再求出每个元素在多少个集合中出现，最后对每个元素出现集合数求和。

集合的异或信息可以用线性基来得到。得到了集合中的一组线性基后，那些不是基的元素无论怎么异或，都可以用这组基得到，也就是和某些基在一起是线性相关的，也就是异或和为0。假设基的大小是$r$，那么还剩$n - r$个不是基的元素。对于每一个剩下的元素分别讨论贡献。$n - r$个元素中，某个元素一定存在的集合数有$2^{n - r - 1}$2^{n - r - 1}$$个。对于每个这样的集合，我都可以选取一些基，使得最后的集合异或和为0。因此，这些元素的贡献都是$2^{n - r - 1}$。

现在要单独讨论剩下的$r$个作为基的元素了。算这$r$个元素的贡献的方法是类似的，如果除掉其中某个元素外，剩余的$n - 1$个元素又构成了一个空间，又选出了一些基，则这个单独的元素又可以被新的基所表示，这个元素的贡献同样是
$2^{n - r - 1}$。

但是，如果运气不好，$r$个基中的某个元素是必不可少的一个基。少了这个基，整个空间就少了一维。换句话说，谁和它的异或和都不能为0。在这样的情况下，这个元素就毫无贡献了。

那么对于作为基的$r$个元素，我们的任务就是判断它们是否可以被任意一个其它的基所表示。对于某个基，有一种很简单的方法能构造出其它$n - 1$个元素的基。先构造出$n - r$个元素的基，它们代表了剩余$n - r$个数的空间。再把$r$个基中除了当前这个基外的$r - 1$个基也加入这个新的空间里面。现在，这个空间就能代表剩下$n - 1$个数了。判断选出的这个基是否在新的空间里即可。

Review

在写这题之前我是不会线性基的，但稍微学了一下就发现，只要学过了线性代数的话很快就能理解线性基。只要理解了线性基，那么这题就非常简单了。

不过这题的一个关键是把问题从求集合大小转换成求每个元素出现集合数。这个转换十分关键。我由于是看着题解写的，没有在这个问题上碰到障碍。但若是要在比赛中快速把难求的问题转换成容易求的问题，就需要极高的解题灵活度了。这种能力只有通过大量写题目才能获得。这也是大量刷题培养手感的意义所在吧。

I Points Division

Description

给$n$个点，每个点有$a,b$两种价值。现在要把所有点分成两个部分$A,B$，要保证$\neg \exists p_i \in A, p_j \in B,x_i \geq x_j \bigwedge y_i \leq y_j$。在$A$里面的点算$a$价值，在$B$里面的点算$B$价值。求最大价值和。

数据范围：
$1 \leq n \leq 10^5$
$1 \leq x_i, y_i, a_i, b_i \leq 10^9$
$所有点互异$

Solution

显然，我们要做的第一件事就是把划分$A,B$的条件弄得更直观一些。题目的要求是：没有两个点，使得左上角的点属于$B$，右下角的点属于$A$。也就是说，如果一个点被分配进了$B$，那么它右下角的所有点都得进入$B$；如果一个点被分配进了$A$，那么它左上角所有的点都得进入$A$。

也就是说,空间被分成了左上角和右下角两部分。那么是谁把空间划分的呢？仔细一想，划分空间的应该是一条折线。折线左上角的点属于$A$，折线右下角的点属于$B$。不妨再规定一下，折线上面的点都属于$B$（同一种划分下，如果折线上的点属于$A$的话，会得到另一条不同的折线，但效果是一样的）。这条折线是从左下向右上的，也就是随着x的增长y是不减的。

分$A,B$算价值太麻烦了。不妨假设所有点最开始都属于$A$，然后我们试图让一些点加入$B$，使得总价值能够有所增长。这样的话，每一个点的价值就唯一了，新价值是$b - a$。

之后要统计结果并保证不重复，不妨尝试对所有点从左到右进行统计。

如果选择了一个点，那么$x$坐标大于等于它且在它下方的点一定也要被加入，也要统计答案。而只要唯一确定了一条折线，我们就确定了一种方案。因此，我们只要考虑折线上的关键点有哪些，让那些右下角的点在计算关键点的时候被计算到。我们从左到右考虑每个点作为关键点的结果。但如果在把当前点加入的同时就想统计右边所有的点，并立刻算出答案，那么再考虑下一个点时，它就不好知道右边有哪些点已经被左边之前的点计算过了。所以，在考虑加入一个关键点的时候，不能立刻算出它的最终贡献，只能考虑在所有已经访问过的点中，它的临时答案。而经过后面那些点时，后面的点会对之前所有$y$坐标大于等于它的临时答案都加上自己的贡献，因为这些点被强制加入了。在讨论当前进入$B$的点时，不直接计算所有右下角的点，而是反过来，先计算一个临时答案，等碰到了右下角的点再加上它们的贡献。这种统计方式是本题的关键。

对于一个关键点，我们已经能统计它右下角的点了，现在来考虑如何计算当前点的临时答案。如果把一个点放到折线上，那么之后下一个点无论怎么选点，都与折线上左边的点无关，而只与现在选的这一个点有关。这表明了选择折线时的子结构性质。既然如此，我们把当前点放到折线上时，也不用管以前的点，只要选一个最优的上一个点就行了。这里的最优，指的是临时答案的最优。对每个点选择上一个点的过程，和动态规划的过程是一样的。发现最优子结构性质，是本题的第二个关键。

现在我们已经可以得到一个正确的算法了：从左到右，从上到下（这个很关键）地枚举每一个点，讨论它作为折线上的点时的情况。对每个点，考虑所有之前走过的，且$y$坐标小于等于它的点（要保证能和这个点构成不降折线），从中选一个临时答案最大的点作为这个点的上一个点。此时，新的这个点的临时答案和上一个点是一样的，因为我们还没有考虑新的这个点自己还有它右边和下面的点。我们把这个点的临时答案也写入记录里面。最后，把已经访问过的，且$y$坐标大于等于它的所有点的临时答案都加上新的这个点的价值，表示这个点对之前所有$y$坐标大于等于它的点的贡献。只要对每个点都进行上述的操作，等处理完最后一个点后，每个点的临时答案就变成了最终答案。从所有最终答案选一个最优的就是题目的答案了。

但是，这样的话时间复杂度似乎不能接受。遍历每个点肯定要右$O(n)$，讨论之前所有点并修改临时答案是$O(n)$，总的时间复杂度是$O(n^2)$，肯定会超时。我们必须优化一下从之前点找最优值以及修改值的过程。

我们可以发现，我们在找之前所有点和修改答案时，都是在访问$y$坐标连续的点。找最大临时答案是找所有$y$小于等于当前点的点，修改是修改$y$大于等于当前点的点。那么，我们可以把所有点的临时答案按照$y$坐标的顺序存储。我们存的不再是某个点答案，而是某个$y$坐标的答案，这样我们依然不会漏掉某些情况：如果后面出现了一个和前面$y$坐标相同的点，如果选了之前的点的话，后面这个点一定要选到。因此，不存在不选新的这个点而只选前面那个点的情况，我们可以放心大胆地覆盖掉之前那个临时答案。现在所有答案都存到了$y$轴上。对于连续区间的修改、查询，我们就可以用线段树来维护了。线段树完成区间加一个值、找到区间最大值这两个操作就行了。

$y$坐标的范围是$[1,10^9]$，读完数据后离散化一下就可以了。

最终时间复杂度是$O(nlogn)$

Review

这道题考察的知识不难，但对问题的思考、分析是本题的难点，在修改哪些点、访问哪些点、如何选择枚举方向等一些细节上也需要多加注意。我感觉这道题出得非常好。

我自己写的时候犯的错误只有搞错了从左到右，从上到下的枚举方向，其它部分都很顺利。由于我是看了题解后再写的，少了很多对于问题的思考、分析，我不能保证下次碰到同样难度的题目也能写出。只能说，很多题目用的算法、数据结构大家都会，但是要把问题转换到能用熟悉的方法来解决的那一步，不需要太多的经验积累，而需要对问题做出正确的分析。碰到难题要敢去想。

在过去的半年里，由于自己和外部的种种原因，我没有认真地进行ACM训练。用愧疚来形容我的感受的话，或许有一些夸张。更多的感受或许是无奈与遗憾。

但是，暑假ACM集训即将开始了。这或许是我人生中最后一段能够把全部精力投入算法竞赛的时光。每天不需要考虑太多，只是享受思考与解题的快感就好。

为了能够让自己更有动力，更有目标性，我决定开一篇文档来记录自己的刷题成果。我在这个暑假计划写完200道题。每场比赛都能补7~8题的话，就已经能够完成150题了，可见这个目标的达成并不困难。但是，我希望我写每一道题都能认真地去思考，有质量地完成，并顺便补习题目中出现的不会的知识。

9.7：虽然暑假过了，但是过题清单统计到所有网络赛打完吧

9.17：虽然我没有完成我的目标，但我这个暑假还算是投入了很多精力在ACM上，学到了不少了东西的。开学后做的题目会另开一个文章来存。

下面是每道题完成的情况及题解链接（如果有题解的话）：

下划线表示这道题很有价值/我很喜欢

进度(120/200)

7.18

共计4题
2019牛客1A（笛卡尔树)
2019牛客1B（数学）
2019牛客1F（找规律）
2019牛客1J（水）

7.19

共计4题
2019牛客1C（贪心、数学）
2019牛客1E（贪心、dp）
2019牛客1H（线性基）
2019牛客1I（二维点，线段树）

7.20

共计2题
2019牛客2F（蛮力搜索)
2019牛客2H（单调栈）

7.21

共计8题
2019CCPC江西省赛1
2019CCPC江西省赛4
2019CCPC江西省赛6
2019CCPC江西省赛7
2019CCPC江西省赛8
2019CCPC江西省赛9
2019CCPC江西省赛10
2019CCPC江西省赛11
(今天题比较水)

7.22

共计3题
2019HDU多校1-2（区间异或和最大）
2019HDU多校1-4（思维）
2019HDU多校1-9（序列自动机、贪心）

7.24

共计5题
2019HDU多校1-1（dp）
2019HDU多校1-12（组合数学、卷积）
2019HDU多校2-I（回文树）
2019HDU多校2-J（签到）
2019HDU多校2-K（可持久化线段树）

7.25

共计1题
2019牛客3-F（st表、双向队列维护区间最值）

7.26

共计4题
2019牛客3-G（笛卡尔树上区间二分）
2019HDU多校1-6（后缀自动机）
2019HDU多校2-H（最小割）
2019HDU多校2-L（线段树维护信息）

7.27

共计3题
2019牛客4-A（树形DP）
2019牛客4-I（后缀自动机、回文树）
2019牛客4-J（分层图（令边权为0））

7.28

共计2题
2019HDU多校2-F（FWT）
2019牛客4-C（笛卡尔树、区间最值）

7.29

共计2题
2019HDU多校3-4（二分、线段树/平衡树）
2019HDU多校3-7（二分、线段树/平衡树）

7.30

共计2题
2019HDU多校1-11(莫比乌斯反演)
2019HDU多校2-E(期望、简单dp)

7.31

共计3题
2019HDU多校4-3（思维）
2019HDU多校4-7（结论题）
2019HDU多校4-8（二分、可持久化线段树）

8.1

共计3题
2019牛客5-G（中等dp）
2019牛客5-F（思考、补图、二分图最小覆盖方案）
2019牛客5-H（字符串前后关系转化成对图求环）

8.3

共计4题
2019牛客6-D（暴力模拟）
2019牛客6-E（构造自补图）
2019牛客6-J（简单dp）
2019HDU多校4-6（思维、斜率优化）

8.5

共计1题
2019HDU多校5-6（exkmp签到）

8.7

共计5题
2019HDU多校6-4（两颗权值线段树）
2019HDU多校6-6（曼哈顿距离模意义下性质）
2019HDU多校6-8（暴力）
CodeForeces 674C（斜率优化DP）
2019HDU多校5-1（分母最小的给定范围下的分数）

8.8

共计4题
2019牛客6-A（最小表示法暴力DP）
2019牛客6-B（三次以上多项式必可因式分解结论）
2019牛客6-D（签到）
2019牛客6-H（繁琐的数位DP）

8.9

共计5题
Comet8-A（签到）
Comet8-B（签到）
2019HDU多校6-2（随机数据、LIS、暴力重构）
2019HDU多校6-5（线段树维护最大子段和）
2019HDU多校6-12（签到）

8.10

共计1题
2019牛客8-C（找规律）

8.11

共计7题
Comet8-C（dp或者线段树维护最大子段和）
Comet8-D（思考、树状数组）
2019牛客8-A（单调栈、最大矩形去重）
2019牛客8-B（签到、单独考虑贡献）
2019牛客8-D（暴力BFS重构最短曼哈顿距离）
2019牛客8-G（签到）
2019牛客8-J（组合数学、容斥原理）

8.12

共计1题
2019HDU多校7-8（思考）

8.13

共计5题
2019HDU多校7-1（高精度模拟）
2019HDU多校7-6（思维）
2019HDU多校7-7（思考、dp、二分转移）
2019HDU多校7-10（思维、map排序）
2019HDU多校7-11（期望dp）

8.14

共计3题
2019HDU多校8-4（构造）
2019HDU多校8-9（离散化后DFS）
2019HDU多校8-11（思维）

8.15

共计2题
2019牛客9-B（模意义方程、二次剩余）
2019牛客9-E（并查集）

8.17

共计6题
2019牛客10-B（递归）
2019牛客10-D（Java写的中国剩余定理）
2019牛客10-F（线段树维护最值）
2019百度之星初赛-1（签到）
2019百度之星初赛-2（签到）
2019百度之星初赛-5（找规律）

8.18

共计3题
cf-A (水题)
cf-B (无向图最短环)
2019HDU多校8-6（树形dp）

8.19

共计1题
2019HDU多校9-3（硬核折半搜索+基数排序）

8.21

共计2题
2019HDU多校10-3（简单概率）
2019HDU多校10-9（签到DFS）（全场一血）

8.23

共计1题
2019CCPC网络赛1（签到）

8.31

共计6题
2019百度之星复赛-A（树形dp）
2019百度之星复赛-B（思维）
2019百度之星复赛-C（贪心）
2019银川网络赛C（签到）
2019银川网络赛D（猜结论概率）
2019银川网络赛H（贪心排序）

9.1

共计3题
2019南京网络赛B（欧拉降幂）
2019南京网络赛F（区间最值）
2019南京网络赛G（组合数学）

9.7

共计4题
2019徐州网络赛G（回文树）
2019徐州网络赛I（区间询问，固定右端点）
2019徐州网络赛L（打表，TSP问题）
2019徐州网络赛M（序列自动机贪心）

9.8

共计2题
2019银川网络赛重赛E（水）
2019南昌网络赛E（约瑟夫问题）

9.9

共计3题
min_25筛入门题X3

9.14

共计2题
2019沈阳网络赛F（二分查找）
2019沈阳网络赛G（物理）

9.15

共计3题
2019上海网络赛B（离散化、区间异或）
2019上海网络赛C（FFT、简单容斥、不同数据量不同算法）
2019上海网络赛E（指数生成函数）

递推关系与生成函数

递推关系

斐波那契数列通项

俗话说，斐波那契数列的通项是：

$\frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n (n \geq 0)$

看上去如此玄妙的式子是怎么推出来的呢？

我们都知道，斐波那契数列是:$0,1,1,2,3,5,8,13,21,34,55…$。规律是，从第三项开始，后一项等于前两项之和，即$h_n = h_{n - 1} + h_{n - 2} (n >= 2), h_0 = 0, h_1 = 1$。通过观察，我们发现这个数列增长得十分快，速度似乎和指数函数差不多。因此我们产生了大胆的假设：假设$h_n = a^n$。

由通项公式：$h_n = h_{n - 1} + h_{n - 2}$,$a^n = a^{n - 1}+a^{n - 2}$。由于此时$n\geq2,a_n\neq0$，式子化简为:

$$\begin{aligned} a^2 &= a + 1 \\ a^2 - a-1 &= 0\\ a &= \frac{1 \pm \sqrt{5}}{2} \end{aligned}$$

$h_n$有多个解，这些解的线性组合同样满足条件。因此可以将解表示为$h_n = c_1(\frac{1 + \sqrt{5}}{2})^n + c_2(\frac{1 - \sqrt{5}}{2})^n$。注意到还有条件$h_0 = 0, h_1 = 1$没有使用。等式有两个，未知数也有两个，因此可以解出$c_1, c_2$来：

$$\left\{ \begin{aligned} & 0 = c_1 + c_2 \\ \\ & 1 = \frac{1 + \sqrt{5}}{2}c_1 +\frac{1 - \sqrt{5}}{2}c_2 \end{aligned} \right. \\$$

解得：

$$\left\{ \begin{aligned} & c_1 = \frac{1}{\sqrt{5}} \\ \\ & c_2 = -\frac{1}{\sqrt{5}} \end{aligned} \right.$$

所以就得到了开头说的那个通项公式。

可以发现，解通项公式的过程和求常系数线性微分方程的方法是类似的，碰到一些的问题的处理方式也是类似的。

常系数线性齐次递推关系

通过上述的斐波那契数列的通项的求解，我们已经可以感受到递推关系的解法了。

若某序列$h_i$满足递推关系$h_n = a_1 h_{n - 1} + … + a_k h_{n - k} + b$，其中$a_i,b$可能依赖于$n$,$a_k \neq 0$，则称序列满足k阶线性递推关系。若$b = 0$，则还称它是齐次。若$a_i$都是常数，则称它还是常系数。正如标题所讲，本节讨论常系数线性齐次递推关系。

由递推关系得到的方程$x^k = a_1x^{k - 1} + … a_k$被叫做特征方程。特征方程的k个根叫特征根，一个特征根对应一个原递推关系的解。如果p是根，则$p^n$是$h_n$的一个解。如果p是二重根，则$p^n,np^n$是$h_n$的解，依此类推。$h_n$解的最终表达形式是每个特征根对应的解的线性组合。如果此时数列$h_n$有初始值，那么再解个多元一次方程，就可以完全求出$h_n$的通项了。

综上，求常系数线性齐次递推关系就是先解一个一元多次的特征方程，求出数列的表达形式，才根据初始条件解一个多元一次方程，得到数列的通项。

常系数线性非齐次递推关系

由于特征方程有多个根，因此递推关系有多个解，这些解要以通解的形式写出来。而某一个单独能满足条件的递推关系叫做特解。又根据叠加原理，$h_n + a_1 h_{n - 1} + … + a_k h_{n - k} = b$和$h_n + a_1 h_{n - 1} + … + a_k h_{n - k} = c$的解加起来，就是$h_n + a_1 h_{n - 1} + … + a_k h_{n - k} = b + c$的解。因此对于一个常系数线性非齐次递推关系，不用再像之前一样直接求出通解，而是只要求出一个特解，再加上齐次情况的通解，就可以得到该递推关系的特解。我们现在要完成的任务就是求常系数线性非齐次递推关系的特解。

求非齐次的特解我只知道公式，不理解公式的由来，这里就直接给公式了。若：

$$h_n + a_1 h_{n - 1} + ... + a_k h_{n - k} = r^n(b_qn^q +b_{q - 1}n^{q - 1} + ...b_0)$$

则将

$$(c_0 + c_1n+..c_qn^{q})r^n$$

代入$h_n$，解出这些$c$来，就可以得到一个特解。如果$r$还是特征方程的根，且是$m$重根，则要代入

$$(c_0 + c_1n+..c_qn^{q})r^nn^m$$

可以看出，求特解时，就是把等式右边的非齐次项按$r^n$的指数分个类。再顺便看一下$r$是否是特征方程的解，若是的话要乘上$n$的次方项。特解的未知数个数取决于非齐次项中的多项式的次数，把这个式子套回去可以解出所有的未知数来。具体看下面的例子。

例：求$h_n = 2h_{n - 1} + n^2$的特解。
解：
特征方程：

$$x = 2$$

将

$$c_0 +c_1n+c_2n^2$$

代入得：

$$\begin{aligned} c_0 +c_1n+c_2n^2 &= 2 (c_0 +c_1(n-1)+c_2(n - 1)^2)+n^2 \\ c_0 +c_1n+c_2n^2 &= 2 c_0 + 2c_1n - 2c_1+ 2c_2n^2 - 4c_2n + 2c_2 + n^2 \\ (c_0 - 2c_0 + 2c_1 - 2c_2) + (c_1 - 2c_1+4c_2)n + (c_2 - 2c_2 - 1)n^2 &= 0 \end{aligned}$$

上式恒成立，因此：

$$\left\{ \begin{aligned} c_0 - 2c_0 + 2c_1 - 2c_2 &= 0 \\ c_1 - 2c_1+4c_2 &= 0 \\ c_2 - 2c_2 - 1 &= 0 \end{aligned} \right.$$

解得：
$
\left\{
\begin{aligned}
c_0 &= -6 \\
c_1 &= -4 \\
c_2 &= -1
\end{aligned}
\right.
$

得到一个特解：
$h_n = -6 - 4n - n^2$

生成函数

生成函数的用处

若有一个数列$h_0,h_1,h_2…$，则它的生成函数定义为$g(x) = h_0 + h_1x + h_2x^2…$。若数列是无穷的，则这个级数也是无穷的。

生成函数乍看上去非常奇怪，因此必须要先理解生成函数是用来做什么的。生成函数正是为了解决一些问题而定义出来的。

设$h_n$为从集合$\{2a\}$中取出n个字母的方案数，则数列为$1,1,1,0,0…$，生成函数$g_1(x) = 1 + x + x^2$。同理，从集合$\{3b\}$中取出n个字母的方案数得到的生成函数$g_2(x) = 1 + x + x^2 + x^3$。那么现在，从集合$\{2a,3b\}$中取出n个字母的方案数得到的生成函数是什么呢？

还是先求出方案数序列。$h_0 = 1,h_1 = |\{a,b\}| = 2, h_2 = |\{aa,ab,bb\}| = 3,h_3 = |\{aab,abb,bbb\}| = 3, h_4 = |\{aabb,abbb\}| = 2, h_5 = |\{aabbb\}| = 1$。则其生成函数$g(x) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5 = (1 + x + x^2)(1 + x + x^2 + x^3) = g_1(x)g_2(x)$。“巧合”发生了。一个问题的解的生成函数等于子问题的解的生成函数相乘。

生成函数的本质，就是把“总和”为$n$的方案数放到$x^n$的系数上。多项式在进行乘法时，会很自然地进行排列组合，排列组合计算的结果依然保留在系数上。我目前的理解是，生成函数就是用来计算排列组合的。

生成函数既然是用来计算排列组合的，但我们现在都是在通过排列组合反推生成函数。如果是用多个生成函数的乘积来计算总的生成函数，再算出方案数，那么我们还是要手动进行多项式乘法，这个过程和我们算排列组合的过程是一样的，计算量完全没有减少。那么，生成函数到底有什么用呢？

当生成函数是无穷级数时，生成函数的形式就美观了许多，比如：

$$\begin{aligned} \frac{1}{1-x}&=1+x+x^2+x^3... \\ \frac{1}{(1-x)^k}&=\Sigma\ _{n = 0}^{\infty}\tbinom{n + k - 1}{k - 1}x^n (由多重集的组合公式)\\ e^{x} &= 1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!} +... \\ e^{-x} &= 1 - \frac{x}{1} + \frac{x^2}{2!} - \frac{x^3}{3!} +... \\ \end{aligned}$$

这样，再求一个复杂的排列组合时，可以先求出简单的子问题的生成函数，才把这些生成函数相乘。当生成函数是无穷级数的时候，往往能进行某些化简。求最终的生成生成函数的某个系数，就可以得到对应的方案数。

看一道经典例题：
例：确定苹果、橘子、香蕉和梨的袋装水果的袋数$h_n$的生成函数，其中各袋要有偶数个苹果，最多两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出$h_n$的公式。
解：

$$\begin{aligned} g(x) &= (1 + x^2 + x^4 + ...)(1 + x + x^2)(1 + x^3 + x^6 + ...)(1 + x) \\ &= \frac{1}{1 - x^2}\frac{1}{1 - x^3}(1 + x + x^2)(1 + x) \\ &= \frac{(1 + x + x^2)(1 + x)}{(1 - x^2)(1 - x^3)} \\ &= \frac{(1 + x + x^2)(1 + x)}{(1 - x)(1 + x + x^2)(1 - x)(1+x)} \\ &= \frac{1}{(1 - x)^2} = \Sigma\ _{n = 0}^{\infty}\tbinom{n + 1}{1}x^n \end{aligned} \\$$

$\therefore h_n = n + 1$

指数生成函数

在求多重集合的排列问题，比如从集合$\{2a,3b\}$中能拼出多少个长度为3的单词这样的问题时，我们要先求出各种组合的方案，除以每个数出现次数的阶乘，最后再乘上总数的阶乘。生成函数既然是解决排列组合问题的，自然也能解决此类多重集排列问题。在刚才的生成函数的基础上，加上我们平时求多重集排列的方法，就得到了指数生成函数的概念。

类似地，对于序列$h_n$，其指数生成函数定义为$g^{(e)}(x) = h_0 + h_1\frac{x}{1} + h_2\frac{x^2}{2}…$。由于在分母上除了一个阶乘，生成函数很容易变成$e^x$之类的形式，大概指数生成函数的名字就是这样得来的。$x^n$前面的系数再乘一个$n!$就是多重集n排列的方案数。

用法看例题即可快速理解：
例：如果偶数个方格被涂成红色以及奇数个方格被涂成白色，试确定用红、白、蓝和绿为1行$n$列棋盘的方格着色的方案数$h_n$。
解：

$$\begin{aligned} g^{(e)}(x) &= (1+\frac{x^2}{2!}+\frac{x^4}{4!}+...)(\frac{x}{1}+\frac{x^3}{3!} + ...)(1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!} +...)^2 \\ &= \frac{(e^x + e^{-x})}{2}\frac{(e^x - e^{-x})}{2}e^{2x} \\ &= \frac{e^{4x}-1}{4} \\ &= \Sigma_{n = 0}^{\infty}\frac{4^nx^n}{4n!} - \frac{1}{4}\\ \end{aligned}$$

$\therefore h_0 = 0, h_n = 4^{n - 1}(n \geq 1)$
无穷级数带了一个常数项，因此通项在0的时候要单独写出来。

ACM中也有一些题要用到生成函数的思想，但解题时最后还是要用FFT。等以后碰到了相关的题目，我会把题解写在ACM分类中。

递推关系与生成函数

用生成函数解递推关系

好吧，生成函数还是有其他用途的，比如求解递推关系。不然为什么课本把这两个概念放在同一章呢？

只用一道例题来说明用生成函数求常系数线性齐次递推关系的方法：
例：
求$h_n - 5h_{n - 1} + 6h_{n - 2} = 0,h_0 = 0, h_1 = 1, h_2 = 5$的解。
设数列的生成函数为$g(x)$，可以得到：

$$\begin{aligned} g(x) &= h_0 &+ h_1x &+ h_2x^2...+h_nx^n \\ -5xg(x) &= &- 5h_0x &- 5h_1x^2...-5h_{n - 1}x^n \\ 6x^2g(x) &= & &+6h_0x^2...+6h_{n - 2}x^n \\ \end{aligned}$$

把上面三个式子左右相加，由$h_n - 5h_{n - 1} + 6h_{n - 2} = 0$：

$$\begin{aligned} (1 - 5x - 6x^2)g(x) &= h_0 + (h_1 - 5h_0)x \\ (1 - 5x - 6x^2)g(x) &= x \\ g(x) &= \frac{x}{1 - 5x - 6x^2} \\ g(x) &= \frac{1}{1 - 3x} - \frac{1}{1 - 2x} \\ g(x) &= (1 + 3x + 3^2x^2 +...) - (1+2x+2^2x^2+...) \end{aligned}$$

$\therefore h_n = 3^n - 2^n$

虽然感觉这种方法很高大上，但是比起直接解特征方程来，这种方法还是太麻烦了。既然如此，我们是不是可以不用生成函数来解递推关系的问题了？

当然不是。仔细看一下上面的解题过程，我们求解递推关系完全是在对生成函数$g(x)$做各种各样的操作，好像和递推关系是否线性、齐次什么的一点关系也没有。对于最开始特征方程法解不了的一些递推，用生成函数可能可以解出来。不妨看下面一个问题：

例：（Catalan数）对于一个有$n$个节点的二叉树，在保持左右子树的有序性，即不考虑任何变换的情况下，有多少种可能的形态？（比如$n = 2$时有两种，一个节点是根，另一个节点是根的左儿子或者右儿子）

解：
为了方便，记$n$个节点的二叉树的形态数为$h_n$。

考虑把问题转换成子问题。当现在有$n$个节点时，我们需要先选一个节点为根，再把剩下的节点放到根的左右子树中。如果根的左子树放了$a$个节点，那么右子树就要放$n - 1 - a$个节点，也就是说左右子树的节点和一定是$n - 1$。在这种情况下，问题就变成了两个子问题：$a$个节点的二叉树和$n - 1 - a$个节点的二叉树有多少个？我们把这两个数算出来，再一乘，就是当左边放$a$个节点时，$n$个节点的二叉树的形态数。

当然，我们不能只算$a$个节点，因为根左右子树的节点数可能是$0, 1，2，3…n - 1$。因此我们要讨论所有情况，并且把每种情况下的总情况数算出来，再进行累加。因此可以得到递推公式:

$h_n = \Sigma_{i = 0}^{n - 1}h_{i}h_{n-1-i}$

特别地，这里要令$h_0 = 1$。

由于这个递推关系根本不是线性的，我们无法用特征函数来解。考虑用生成函数$g(x)$来表示数列的每一项，即：

$g(x) = \Sigma_{i = 0}^{\infty}h_ix^i$

突然，我们发现：

$g^2(x) = h_0 + (h_0h_1 + h_1h_0)x + (h_0h_2 + h_1h_1 + h_2h_0)x^2 + …$

每一项中x的系数在递推公式中都可以找到。把递推公式代入式子：

$g^2(x) = h_0 + h_2x + h_3x^2 + …$

由于$h_0 = h_1 = 1$：

$
\begin{aligned}
g^2(x) &= h_1 + h_2x + h_3x^2 + … \\
&= \frac{1}{x}(h_1x + h_2x^2 + h_3x^3 + …) \\
&= \frac{1}{x}(g(x) - h_0) \\
&= \frac{1}{x}(g(x) - 1) \\
xg^2(x) &= g(x) - 1 \\
\end{aligned}
\\
\begin{aligned}
xg^2(x) - g(x) + 1 &= 0 \\
g(x) &= \frac{1 \pm \sqrt{1-4x}}{2x}
\end{aligned}
$
由于$h_0 = 0$，$g(x) = \frac{1 - \sqrt{1-4x}}{2x} = \frac{1}{x}(\frac{1}{2} - \frac{1}{2}(1 - 4x)^{1/2})$

根据牛顿二项式定理：
$
\begin{aligned}
(1 + x)^{1/2} = 1 + \Sigma_{n = 1}^{\infty}\frac{(-1)^{n - 1}}{n\times 2^{2n-1}}\tbinom{2n - 2}{n - 1}x^n
\end{aligned}
$

所以：
$
\begin{aligned}
(1 - 4x)^{1/2} &= 1 + \Sigma_{n = 1}^{\infty}\frac{(-1)^{n - 1}}{n\times 2^{2n-1}}\tbinom{2n - 2}{n - 1}x^n(-4)^n \\
&= 1 + \Sigma_{n = 1}^{\infty}\frac{(-1)^{1}}{n\times 2^{-1}}\tbinom{2n - 2}{n - 1}x^n \\
&= 1 - 2\times \Sigma_{n = 1}^{\infty}\frac{1}{n}\tbinom{2n - 2}{n - 1}x^n
\end{aligned}
$

套回开始的式子中:
$g(x) = \Sigma_{n = 1}^{\infty}\frac{1}{n}\tbinom{2n - 2}{n - 1}x^{n - 1}$

所以，$h_n = \frac{1}{n + 1}\tbinom{2n}{n}$。

如果我们把$h_0$看成第一项的话，那么第$n$项的值就是$\frac{1}{n}\tbinom{2n - 2}{n - 1}$。这个数就是著名的卡特兰(Catalan)数。

在这个过程中，我们完全是在对生成函数进行求解，而没有管递推关系的形式是怎么样的。这其中最妙的一步是发现了$g^2(x)$正好可以得到递推关系中的右半部分，只能说这种解法不是推算出来，而是突发奇想的。

总结

有时候推出来看似花里胡哨的递推关系，只要式子是线性的，就可以利用特征方程的方法求出通项来，从而把O(n)的时间复杂度变成O(1)，把编程问题变成数学问题。

生成函数是用来解决组合问题的，当问固定数量的方案数时，就要想到生成函数了。在求排列时，要利用之前的方法，求出指数生成函数，再在结果前乘一个阶乘。

递推关系对应一个生成函数，可以用生成函数来解递推关系。对普通的线性方程，这种解法太麻烦了，还不如用普通的解法。对于一些比较复杂的递推关系，生成函数才能发挥出它的用途。

计算是什么呢？

数学，一门从数字与计算中出现的学科，在发展到一定阶段后，开始追问起了计算的本质。

数学家们用数学的语言，把“计算”这个早就存在的词语严格定义。用自身定义自身，这正是数学之美。

更令人开心的是，数学家在研究计算的过程中，开创了计算理论这门学科。人们在计算理论的基础上，制造了计算机。再随着计算机的应用不断变广，计算机成了一门单独的学科——计算机科学。

又扯远了。计算理论研究了什么是计算的机器，哪些问题是人们可以计算出来的，可以计算的问题怎么才能计算得更快。为了开始计算理论的学习，我们需要从最简单的计算模型，来一步一步理解计算理论研究的内容。有穷自动机及正则语言，就是我们的第一个学习对象。

第1章 正则语言

事物的状态

每时每刻，世界的万物都在发生变化。比如，昼夜不断交替着，早晨太阳升起，傍晚太阳落下；今天的我，总是比昨天的我更加帅气一点。

有些变化，它变来变去就是那么几种情况。比如，天要么是亮的，要么是暗的。有些变化则不然，是会一直进行下去的。我每天都在变帅，我的帅气程度永远在递增，不会有两个相同的值。

为了更好地掌控那些状态有限的事物，人们用一个有向图来表示这些事物。在有向图中，顶点表示状态，边表示转移条件。比如

黑夜——————-太阳升起————————> 白天
<—————太阳落下———————————-

状态，就是事物本质的情况；状态发生转移，就是外界条件对事物的本质产生了改变。

有限自动机

人们在研究一个数学问题是否可以解决时，想到数学问题涉及的内容都可以转化成字符串。问题解决，就是问题对应的字符串在一系列验证过程后，该字符串被认为是正确的。比如问一个十进制数字是否是偶数，所有问题的输入都转换成一个十进制数字字符串。”1”被认为不是符合要求的字符串,”666”被认为是一个符合要求的字符串。而问题的所有解，则是一个字符串集合，也就是一个语言。

于是人们把数学问题转换成字符串是否“正确”的问题。字符串的每一个字符，都会对字符串是否正确产生影响，都会改变字符串的整体性质。联系开始我。们对于状态有向图的分析，状态转移正是事物本质发生变化的过程。我们似乎可以用开始的状态有向图，来判定一个字符串。因此，人们把字符串的每个字符做为状态转移的条件，把一些状态设为“正确状态”，意味着能通过字符一步一步走到这里的字符串是正确的。当然，还有一个初始状态，表示在什么字符也没有读取时的状态。

这样讲还是抽象了一点，还是举个例子吧。假设我们用的字符全部是0（也就是说字母表是$\{0\}$），我们现在碰到的问题是：给定一串字符串，问其长度是否为偶数。我们该怎么样用一个状态有向图来解决这个问题？或者说，如何把所有解表达出来呢？

从本质上来看这个问题，一串只有0的字符串只有长度为奇数和长度为偶数这两种可能。每多加一个0，就会改变字符串长度的奇偶性。也就是说，我们有两个状态：“偶数长度状态”、“奇数长度状态”。在碰到0的时候，两个状态间会互相转移。最开始时，字符串处于“偶数长度状态”，因为我们读入的字符串长度为0，是个偶数。如果我们读完了字符串后，发现我们停留在了“偶数长度状态”，那么这就说明该字符串的长度是偶数。状态图画出来是这样的：

左上角的箭头表示最开始进入的是q0状态，也就是“偶数长度状态”。右边箭头上的0表示转移碰到0就往箭头的方向转移。左边q0状态里面有一个小圆圈，表示这个状态是最终我们能够认可的状态。

我们构建的这个状态有向图，有一个十分大气的名字“有穷自动机”。这个名字为什么这么叫呢？大概有穷，指的是状态数是有限个。自动机，指的是我们只要把字符串到这个有向图里，按照规则在里面走迷宫，我们最终就可以知道这个字符串是否符合我们的要求。整个有向图就像一个自动工作的机器一样。虽然这个名字看上去很厉害，但正如我们分析的一样，有穷自动机就是一个有向图，它的概念十分容易理解。

每一个有穷自动机都可以由5部分确定：$(Q,\Sigma,\delta,q_0,F)$。$Q$是状态（点）集合，$\sigma$是字母表，$\delta$是转移函数（边）集合，每个转移函数接受的参数是当前状态与碰到的结果，输出的是下一状态，也就是说转移函数集合是$Q\times\Sigma\to Q$。$q_0$是初始状态，也就是我们走迷宫的起点。$F$是接受状态集合，$F\subseteq Q$，也就是迷宫的所有终点。我们需要字母表，是因为无论碰到什么字母，我们都得确切地知道我们下一步该往哪里走。我们在转移函数中，必须写清楚每个字母的转移情况。因此也可以得出，转移函数的集合有$|Q|$行$|\Sigma|$列，代表每个点在碰到每个字母转移到的下一个点。

显然这个定义是数学家给出来的。如果是程序员发明这个东西的话，一定会给每个量取一个好听的变量名，以更好地记忆和理解每个量的意思。不过和其他所有的数学定义一样，这些东西是不用背的，只要理解了它们的意思就好了。这些希腊字母和带下标的字母看起来确实让人头疼。

正则语言与正则运算

有一个很重要的名词，我们明明见过它，却只有现在才能介绍它。正则语言，就是某个有穷自动机可以识别的语言。既然有这个定义，就暗示世界上还有很多语言，很多字符串的集合，是有穷自动机表示不了的。话说回来，作为本章的标题，正则语言竟然是通过有穷自动机定义的，真是没有牌面。

但是，正则语言之所以不叫有穷自动机语言，是因为还有一些概念是“姓”正则的。我们之前讲过，所有数学问题都可以被转换成字符串，问题间的运算就转化成了字符串集合运算，也就是语言运算。比如找到两个问题任一的解，就是这个字符串满足问题一的解或者问题二的解。也就是说，问题转化成了语言求并的过程。类似的，语言还可以互相连接(符号$\circ$)、自我重复（符号$\ast$，所以也被叫做星号)。$A\circ B = \{xy|x\in A \bigwedge y\in B \}$，$A\ast= \{x_1x_2..x_k |k \geq 0 \bigwedge x_i\in A\}$。当然，求并和连接是二元运算，自我重复是一元运算。这三种运算都叫做正则运算。为什么这些也“姓”正则呢？因为正则语言在做了正则运算后，还是正则语言，也就是正则语言在正则运算下封闭。

正则语言在正则运算下封闭这个定理是可以证明的。要证明此定理，要分别证明正则语言在3种运算下封闭。不过在当前条件下，我们比较方便证明的只有求并运算。

定理：正则语言在并运算下封闭。

证明：
设原来的语言为$A_1$,$A_2$，状态集合$Q_1,Q_2$。现在我们构造一个新的自动机的状态集合$Q$，它有$|Q_1|\times|Q_2|$个元素，不妨把它们排成$|Q1|$行$|Q2|$列。其中，第$i$行第$j$列个状态表示处于原来自动机$A_1$的第$i$个状态和$A_2$的第$j$个状态。也就是说，我们在新的自动机上完全模拟出了之前两个自动机的状态。

新自动机字母表是之前字母表的并。在新自动机上，每一列状态都按$A_2$的规则向左右转移，每一行状态都按$A_1$的规则上下转移，如果是碰到某个自动机之前不存在的字母，就转移到一个失败状态——不管碰到任何字符都回到自己，且不是接受状态的状态。初始状态是既处于$A_1$初始状态也处于$A_2$初始状态对应的状态。$A_1$接受状态对应行上、$A_2$接受状态对应列上的所有状态都是新自动机的接受状态。

新自动机表示的语言就是前面两个语言的并。因此正则语言在并运算下封闭。

为了证明另外两种运算，我们还需要一个新的工具。

非确定有限自动机

在一个偌大的迷宫中，路径错综复杂，你会怎么办呢？在毫无办法的情况下，我们只能选择像无头苍蝇一样随便选择下一步了。毕竟，不停地往前走总比站在原地强。

有一类比较任性的有穷自动机，它们在碰到了一个字符后，可能选择往多个地方走，甚至拒绝接受这个字符。它们在某个状态的时候，还没碰到下一个状态，就有可能急不可耐地往其它一些状态触发。这样的有限自动机叫做非确定有限自动机(Nondeterministic Finite Automation,NFA)，之前我们熟悉的有限自动机叫做确定有限自动机(Deterministic Finite Automation, DFA)。为了节约宝贵的时间，后文用简称来称呼它们。

NFA可以看成是一个会影分身的人在自动机上走迷宫。读取到下一个字符后，他可能会召唤多个自己的分身，和自己走不一样的路；可能拒绝接受这个字符，让自己就此消失。没有读取到字符，或者说读取到空字符$\epsilon$时，它也有可能召唤一个分身。只要有一个分身到达了终点，那么他就胜利了，这个字符串就算是接收。如果怎么也走不到终点，或者他的所有分身都消失，那么字符串就算是拒绝。NFA中的非确定性，就是指在碰到某个字符后，下一步的状态是非确定，可能有多个的。

要严谨地定义NFA的话，只需要稍微修改一下开始DFA的定义。DFA的状态转移集合$\delta$的类型是$Q\times\Sigma_{\epsilon}\to P(Q)$。$\Sigma_{\epsilon}$是原字母表中附加一个空字符$\epsilon$，$P(Q)$是$Q$的幂集，也就是$Q$的所有子集的集合。换言之，在每个状态，碰到了某个字符或不碰到字符后，下一步得到的状态是一个集合，而不是单个状态。

配上图的话，理解NFA会更方便。但由于图不好放，这里就不贴了。随便翻开一本计算理论的课本，或者去网上搜索非确定有限自动机，都能找到一些很直观、易于理解的NFA运算过程图。

NFA是如此强大，它用了一种很赖皮的方式来走迷宫：我尝试当前字符串表示的所有路径，有一条能走出去，就算我能走出迷宫。而在原来的DFA上，我们只能按照规则，一边读字符，一边往前走一步。但令人惊奇的是，NFA和DFA是等价的，每一个NFA都可以找到一个和它对应的DFA。我们还是使用构造性发发来证明这个定理，也就是证明每个NFA都可以转换成DFA。DFA可以转换成NFA是显然的，因为根据定义，DFA就是NFA。

我们再次回顾一下NFA的定义。NFA转移函数的结果，从单个状态，变成了状态的集合。转移函数的结果集合，不是状态集合$Q$，而是幂集$P(Q)$。仔细一想，$P(Q)$的大小也只是$2^{|Q|}$个啊！它的大小是有限的。我们可以构造一个新的DFA，它有$2^{|Q|}$个状态，每个状态对应$P(Q)$的一个元素。要得到这个对应的话，只需考虑到计算机科学常用的二进制就行了。用一个$|Q|$位二进制数来表示子集，某一位是1就代表NFA中这一个状态里有一个分身。NFA是$Q$子集与子集之间的转移，但如果我们把子集看成单个元素的话，那么子集转移就等价于状态转移了。

上面这段话其实不是用来读的，是用来启发思考的。对于一个证明，往往要通过自己的思考来理解，看别人的证明思路一般是很难看懂的。相信看到了二进制，二进制每一位对应原NFA中的一个状态，你就能灵光一闪地想出整个证明过程来了。

现在，我们知道NFA和DFA等价，它们只是名字不同的同一事物罢了。DFA的有关性质，NFA都有。比如，能被NFA识别的语言都是正则语言。

嗯？这说明我们以后可能通过NFA来证明语言的正则性了。正好，我们还差两个正则运算的定理没有证明呢！这两个定理可以用一些直观但不严谨的方法证明。

还是把自动机想象成走迷宫，我们将构造出一台NFA，能在新NFA中走到终点的字符串，就是运算过后的字符串。

先证明连接运算的封闭性，即证明有这样一个DFA或NFA，它可以识别连接后的字符串。但我们手里有的，只有识别之前两种语言的DFA或NFA。如果想用DFA来判定连接后的字符串的话，我们首先要面对一个问题：这个字符串应该在哪个位置拆成两半，使得前一半属于第一种语言，后一半属于第二种语言呢？但NFA就没有这个烦恼。先构造两个语言的DFA，取名为A，B。在机器A的所有接受状态中，连一条$\epsilon$的边到B的初始状态，表示任何一个到了A终点的人都可以影分身抵达B的起点。A的初始状态为新机器的初始状态，B的所有接受状态为新机器的接受状态。NFA没有在哪个位置拆开字符串的烦恼——反正我试遍所有可能就行了。

再证明星号运算的封闭性。根据上面的思路，我们可以构造一台NFA，它的所有接受状态，都连一条$\epsilon$的边到初始状态，表示我们在任何时候从可以尝试把这个字符串“拆开”。但是，星号运算中空字符串一定会被接受，因此我们要额外建立一个初始状态，它一个被接收的状态，有且仅有一条$\epsilon$的边指向原DFA的初始状态。

总算，我们证明了正则运算在正则语言下封闭，它们是一家人，有一样的姓也是理所当然的了。

正则表达式

有了正则运算这一新武器，我们有了一个新的表示语言的工具——正则表达式。如果用一个DFA来表示语言，每次都要画一张图，实在是太麻烦了。但是，使用正则表达式的话，我们只需要用一行文字就可以表达语言了。正则表达式和我们的数字表达式一样，运算符号就是并、连接、星号，“数字”就是空字符、空集和单个字符。数学表达式里有1+1=2，正则表达式里有0*0 = {至少有一个0且全部都是0的字符串}。

等等！DFA可以表示语言，正则表达式也可以表示语言，还没有人说它们是等价的呢！但正则表达式也姓正则，暗示它表达的语言就是正则语言，正则表达式等价于DFA。我们接下来又要用构造来证明这一定理。

唉，要是世界上有这样一台机器就好了。机器只有两个状态，第一个状态是初始状态，第二个状态是接收状态。第一个状态到第二个状态的转移条件是一个正则表达式。我要验证一个正则表达式的字符串，就等价于把字符串放入这个机器中判定。可惜我们的DFA只允许在转移条件上写字符啊！

数学家们向来比较开放，喜欢扩大定义。没有这样的机器，我们就来创造这样的机器。广义非确定有限自动机（GNFA)是一个可以把正则表达式当成转移条件的自动机。为了证明正则表达式和DFA的等价，我们只需要一步一步地把DFA的转移条件变成正则表达式，最后变成我们开始说过的那个梦想中的机器——只有两个状态和一行正则表达式的机器。如果能构造出这样的转换方法，就能证明定理了。

我们这次构造的GNFA，是在原来的DFA上一步一步改造过来的。改造的第一步，是新建两个状态——新起始状态$q_s$，新结束状态$q_e$。在保证正确性的前提下，$q_s$对其它每个点连边，每个点向$q_e$。由于正则表达式包括空集，所以连边总是可行的。我们新建的这两个状态就是保留到最后的状态。我们要删掉其它所有点，并修改转移条件，使得整个GNFA依然正确。

对于任意要删的点$q_{rip}$，对于任意其它点$q_i$,$q_j$，设$q_i\to^{R1} q_{rip},q_{rip}\to^{R2} q_{rip},q_{rip}\to^{R3} q_{j}, q_i\to^{R4} q_{j}$，则$q_i$到$q_j$的正则表达式修改为$(R1)(R2)\ast(R3)\bigcup(R4)$。千言万语，胜不过下面这张图：

按照这种方法，我们总能在保证正则表达式的意思不变的情况下把中间点删掉。总有一天，我们会删到只剩$q_s,q_e$两个点，这两个点靠一条正则表达式来转移。

我们说明了DFA可以转换成正则表达式。为了证明等价，我们还得证明正则表达式可以转换成DFA。不过这一步要比开始简单得多。

借助证明NFA与DFA等价的方法，我们用如下方法构造NFA，使之与正则表达式等价。一个字符或者是空字符，就连一条边。空集就不连边。并集就是一个点可以通过空字符$\epsilon$移动到并集所表示的两个部分。星号就是结束部分连$\epsilon$连回初始状态，同时再初始状态前加入一个接收状态。同样，说了这么多，不如放一张图：（声明：该图片来自《计算理论导引》(Michael Sipser)第三版 42页）

DFA和正则表达式互相转化，那它们肯定是等价的了。

非正则语言与泵引理

开始我们提过，正则语言是可以被DFA表达的语言。换言之，还有许许多多的语言无法用DFA表达。举一个经典的例子：设语言$B = \{0^n1^n|n\geq0\}$，也是说该语言表示0和1个数相同，且先出现0再出现1的字符串。仔细一想，你哪怕使出浑身解数，也构造不出识别这种语言的DFA——为了构造一个这样的DFA，我们必须用状态来存储0的数量，但0的数量可以是无穷大，而状态数的有限的。

但有些愣头青喜欢钻牛角尖，他们偏要说道：“我就不管！你构造不出一台DFA，万一别人构造出来了呢？你凭什么说世界上不存在一台DFA识别这种语言？！”

科学家们又想出了一种证明语言不是正则语言的方法，来应对这些“对知识刨根问底”的热心青年。这种方法用了一个引理，叫做泵引理。

如果一种语言$A$是正则语言，那么$\exists (int)p,\forall(string)s\bigwedge|s|\geq p\bigwedge s\in A \Rightarrow \exists xyz = s \bigwedge xy^iz \in A (i \geq 0)\bigwedge |y| > 0\bigwedge |xy| \leq p$。这一行一阶逻辑，能够让人充分复习离散数学的知识。但是，你很可能看完了也看不懂这一行话要干什么，或者干脆跳过了这行话。

泵引理是说，如果A是正则语言，我们可以随便选一个泵长度p。对于A中的每一个很长很长，长度至少是p的字符串，我们都可以把它拆成3份xyz。其中y部分一定非空，且xy加起来很短很短，长度必须小于p。如果我们在中间不断插入y部分，也就是对于任意字符串$xy^iz，i\geq0$,这个字符串还是A的语言。这个引理中有很多存在和任意，需要仔细地多看几遍。

泵引理的正确性的证明十分诡异。我们需要证明，一个正则语言对应的DFA，它满足泵引理的条件。引理说我们可以随便选一个泵长度p，那么不妨令p为$|Q|$，也就是这个DFA的状态数。对于语言中任意一个长度大于等于p的字符串s，它经过的状态大于等于p+1，因为p+1个状态需要通过p次状态转移，也就是需要读取p个字符。s经过了p+1个状态，但我们总共就只有$p = |Q|$个状态啊！这是怎么回事呢？这说明我们至少经过某个状态两次。我在走迷宫的时候，两次走到了同一个地方说明什么？说明我绕路了！我绕了一圈，又返回了原地。既然我经过了某个状态两次，就必然存在一个状态序列，通过这个状态序列可以回到同一个状态。状态的转移需要读取字符，也就是说，读取了一些字符后，我们又回到了之前的某个状态，我们绕路了。这些字符，我把它重复若干遍，我还是会回到这个状态，我永远会在这个状态绕不出去了。这个字符序列，就是我们拆成三部分xyz中的y。在第一次碰到重复字符时，也就是第一次绕路结束时，我们至多有一个状态走了两次，其它每个状态走了一次，也就是说最多走了p+1个状态，也就是最多读取p个字符，这一部分就是xy，$|xy| \leq p$。至此，泵引理得到一个描述性的证明。

可以发现，泵引理中“存在一个p”这句话一点用也没有，因为我们在证明泵引理时，直接把p钦定为状态数|Q|了。

等等，泵引理有什么用啊？泵引理说明如果A是正则语言，则可以干嘛干嘛。我都知道正则语言可以通过构造一个DFA来判断了，我要泵引理干嘛？

泵引理给出的正则语言的必要条件。也就是说，泵引理的逆否命题，得到的是判断一个语言不是正则语言的充分条件。如果一个语言满足泵引理的逆否命题，那么很遗憾，这个语言一定不是正则语言。

或者再从另一个角度上来讲，我们可以通过反证法来证明一个语言不是正则语言。我们把这个语言套进泵引理中，发现它无论如何都会导出矛盾，那么就可以得出这个语言不是正则语言了。

泵引理反过来是这样说的：对于一个语言A，如果对于任意泵长度p，A中存在一个很长很长，长度至少是p的字符串，我们无论如何都不能把它拆成3份xyz，满足下列所有条件：y部分一定非空，且xy加起来很短很短，长度必须小于p。如果我们在中间不断插入y部分，也就是对于任意字符串$xy^iz，i\geq0$,这个字符串还是A的语言，那么A不是正则语言。我们把整个引理取反，所有的存在和任意都反了过来。这就是开始说要注意存在和任意的原因。现在我们也发现，泵长度p不是没有用的。正过来时，p可以任意取值；但反过来说时，p就是任意取值了。泵长度p在证明泵引理时是完全没有用途的，因为它是一个存在的条件，可以任意取值；而在说明一个语言不是正则语言的时候，就要考虑泵长度p为任意值的情况了。

就考试而言，证明一个语言不是正则语言都是一个套路。因为要求证明的命题一定是正确的，所以我们可以无脑套入泵引理来导出矛盾反证。以经典的例子$B = \{0^n1^n|n\geq0\}$来说明一下证明语言不是正则语言的方法。

证明：
假设$B = \{0^n1^n|n\geq0\}$是正则语言。令p为泵长度。随便选择一个字符串$0^p1^p$,它属于B，且长度大于等于p。泵引理保证，它可以拆成3部分xyz，且满足之前的三个条件。由于$|xy|\leq p$，所以$xy$肯定全部由0组成。$xy^iz(i\geq0)$也一定属于B。但很明显，假设我把y重复100遍，由于y非空，xyz的前半部分一定出现了许许多多的0.这样的字符串是不属于B的，矛盾产生。因此，我们假设错误，B不是正则语言。

如果能仔细品味泵引理背后涉及的数学、逻辑原理，我相信人们都会被数学之美、思维之美所打动。这种美看不见摸不着，却深深埋藏在每个人脑中。对于那些爱思考的人来说，发现这些美，就能收获到一种无比的喜悦。能成为一名热爱自己的学科，并能在自己的学科里有所成就的科学家，真是一件令人羡慕的事情。可惜不是人人都适合科研，不是人人都有机遇把自己的一生都献给知识荒原的开拓。

总结一下。这一章讲的是正则语言，也就是可以被有限自动机识别的语言。这一章介绍了许多在后面都会介绍的概念：机器、状态、接收与拒绝、非确定性等。这些概念，是研究后面一些更强大的计算机器的基础。从全书的角度来看，这一章为后续的知识学习奠定了最低层次的基础。同时，这一章也围绕有限自动机，讲了许多实际的内容。有限自动机本身是最低级的计算机器，通过学习它我们能隐隐体会到计算的本质。

从考试的角度来看的话，这一章难点只有两个。一个是DFA向正则表达式的转换，一个是泵引理的理解与证明。而其他部分都不难。自动机名字看上去结构复杂，实际上就是一个有向图，哪怕不知道什么是图，会走迷宫，就能学会有限自动机的概念。非确定有限自动机的概念比较难理解，但一旦理解，一旦迈过那一道坎后，这个概念就会显得十分清晰。所有的证明都不会考，学习它们对于考试毫无益处。

---

后记

我写这篇文章的本意和之前复习概率论一样，是站在讲述者的角度来叙述这些知识，更好地把知识梳理清楚。从结果来看，复习效果是有，但是我花费了大量的时间，而且很多时间都花在了吹牛和一些我已经熟悉的知识的讲解上。而且，考虑到时间不是很够的原因，文章本身的质量也不够高，讲得也不够清楚。也就是说，我花了很多时间，就稍微复习了一些不太熟的知识，文章也没有写好来，总体上来看非常亏。我得到的结论是，复习还是不要写文章的好。如果想清楚地介绍一个知识，就在闲暇的时候慢慢地写文章；如果要复习，就用效率更高的方式来看书。这样复习的话，竹篮打水一场空，什么都没得到。

第五章 大数定律和中心极限定律

考试迫在眉睫，情势刻不容缓，必须快马加鞭，迅速复习完概率论。这一章内容不多，我就不侃侃而谈了，直接把考试会考的内容写出来。若几年后有时间，再补完此处的内容。

第二节 中心极限定律

一句话总结：独立同分布的一堆随机变量之和是正态分布，所以正态分布才在我们生活中那么常见。

例题（BIT 2013 级概率与数理统计试题A 卷）：

Problem

一食品店有三种面包出售,由于售出哪一种面包是随机的，因而售出一只面包的价格是一个随机变量,它取1 元, 2 元, 3 元的概率分别为0.3, 0.5, 0.2. 若售出300 只面包,求售出价格为1 元的面包多于100 只的概率.

Wrong Solution

这不是二项分布嘛！等一下，n是300，这么多？我记得二项分布多了可以转换成泊松分布。这里$\lambda = np = 90$,
$ans = 1 - \sum_{i = 0}^{100}\frac{90^i e^{-90}}{i!}$。虽然我算不出这个数来，但复杂度是$O(N)$，这个答案应该可以接受。

(错误原因：数学题的答案只能用O(1)的算法)

Solution

要求的量满足独立同分布的条件，整体服从正态分布，均值$\mu = 90$,方差$\sigma = 63$。

把100代入$(X - \mu) / \sqrt{\sigma}$转换一下，变成标准正态分布，查一下表，结果为0.8962。

Review

看到一个值由很多简单随机变量相加而成，就把它们当成正态分布来处理。

第四章 随机变量的数字特征

自第二章介绍了随机变量这个概念后，我们一直都在学随机变量的一些性质，或者是从随机变量上定义出来的一些概念。这一章依旧如此。我们将继续学习随机变量的数字特征。标题看起来依然那么高级，但实际内容却十分贴近生活。

第一节 数学期望

赌博是一项自古以来就有的活动。由于赌博失败会给社会安定带来影响，我们是不允许进行金额过大的赌博的。

但是，人还是喜欢赌博。为什么呢？赌博，意味着你花少量代价，就可以获得大量的回报。人在想着大量的回报的时候，就会沉浸于幻想中，而完全忽略了赌博失败带来的后果。

参与赌博的人中，有一些人比较聪明。他们为了赚更多的钱，就开始研究赌博的原理。最终，他们创造了概率论。概率论不仅给我们的生活带来了很多启示，为我们提供了便利，还让我们大二学生的学习生活充满了紧张与压力。

扯远了。现在你需要支付50元，你40%的概率可以得到100元，你和不和我赌博呢？

数学家为了研究自己是赚了还是亏了，怎么赚得更多，就开始研究起这种类型的赌博问题。仔细一想，对于上述的赌博，40%的概率，意味着100局大概有40盘左右是赢钱的。玩100局，可以赚到4000元，但要投入5000元玩。所以，这样的赌博极有可能是亏钱的。

100局赚4000元，平均一下1局赚40块钱。这样一个描述你获得的结果的大概值的东西，就叫做数学期望。可以简称期望。随机变量$X$的期望记为$E(X)$。

刚刚赌博成功与失败，其实就是一个0-1分布。如果赌博多次，就是一个二项分布。显然，期望是属于随机变量的。有了随机变量，就有期望。

从刚刚的例子可以看出，我们用概率乘上随机变量的值，似乎就可以算出期望了。期望的计算方法正是如此。对于离散型随机变量，期望就是所有随机变量的值乘上对应概率再求个和，即对于$P\{X = x_k\} = p_k, E(X) = \sum_{k = 1}^{\infty}x_kp_k$。与之对应，对于连续型随机变量，就是概率密度乘值再求积分，即对于概率密度函数$f_X(x), E(X) = \int_{-\infty}^{\infty}xf(x)dx$。当然，期望存在的前提是，求和或者积分是收敛的。

上面两个式子计算起来可能会很熟悉。事实上，我们之前一直都再对概率p做积分或求和。现在只是在前面乘了一个x后再做运算而已。

期望还有一个名字，叫均值。期望的现实意义和平均数很类似，它们都反映了把整体求和再平均分给每一种情况的值。但是，平均值是对于一些样本而言的，而我们算期望只是从理论出发，对一个已知的分布进行计算。后面数理统计会再讲到平均值。

$E(X)$可以看成一个记号，但把它看成一个函数就更加准确了。输入一个随机变量$X$，就可以输出一个期望值$E(X)$。既然这是一个函数，一种运算，那么它就有一些运算的性质。由于期望的定义比较简单，以下性质就直接列出来了：

(1)$E(C) = C$ ($C$为常数) //常数都不是会变的量，在任何时候值都不变
(2)$E(CX) = CE(X)$ //做期望的时候是在做加法，每个数都乘了一个常数的话，这个常数可以作为公因子提出
(3)$E(X+Y) = E(X)+E(Y)$ //期望是加法，中间可以拆开来
(4)$E(XY) = E(X)E(Y) \Longleftarrow XY独立$ //易证

第二节 方差

在某项竞技项目中，可能两个人平均水平相当（或者说整体的水平和相当），但是两个人给人的感觉不同。一个人时而独挑大梁，时而一声不响；另一个人稳稳当当，每次表现得都差不多。我们把前者叫做浪，后者叫做稳。真正厉害的人应该稳重带浪，浪中带稳。看似波澜不惊，时则暗流涌动。

扯远了。上述现象表明，事情除了整体表现的好坏之外，表现是否稳定也是一个重要的评判标准。

怎么衡量这种不稳定呢？试想一下，如果做出一个稳健的人和一个不稳健的人的“表现-比赛场次折线图”，稳健的人的曲线肯定在中间某条线附近略有波动，而不稳健的人的曲线一定陡峭曲折，时上时下。这个不稳定的值和平均表现有关，也与表现的差值有关。

显然，用$X - E(X)$可以得到表现与期望的差值,这个差值可以反映出表现的波动情况。为了消除负数的影响，人们把$E((X - E(X))^2)$定义为方差，也就是每次表现与期望之差的平方，再求一次期望。方差记为$D(X)$。

方差定义的式子十分便于理解：看一看每个数和期望值的差距，把这种差距累加起来，再平均一下。但这个式子并不是很好用。注意到$E((X - E(X))^2) = E(X^2 - 2XE(X) + E^2(X)) = E(X^2) - 2E^2(X) + E^2(X) = E(X^2) - E^2(X)$。这个式子清爽多了。

方差和均值一样，可以看成是一个函数，同样有一堆的性质：

(1)$D(C) = 0$ //不会变的东西哪有不稳定性呢？
(2)$D(CX) = C^2D(X)$ //平方导致的结果
$D(X + C) = D(X)$ //移动一下又不会改变波动的幅度
(3)$D(X + Y) = D(X) + D(Y) + 2(E(XY) - E(X)E(Y))$
证明：

$$\begin{aligned} D(X + Y) &= E((X+Y)^2) - E^2(X + Y) \\ &= E(X^2) + 2E(XY) + E(Y^2) - (E^2(X) + 2E(X)E(Y) + E^2(Y)) \\ &= (E(X^2) - E^2(X)) + (E(Y^2) - E^2(Y)) + 2(E(XY) - E(X)E(Y)) \\ &= D(X) + D(Y) + 2(E(XY) - E(X)E(Y)) \end{aligned}$$

由于XY独立的时候，$E(XY) = E(X)E(Y)$，上式最后一项为0，式子可以简写为$D(X + Y) = D(X) + D(Y)$

$(E(XY) - E(X)E(Y))$这个东西和XY的独立性似乎有关。下一节会用到这个东西，我不得不把这个式子证了一下。

有了期望、方差这两大武器，我们可以挖掘出随机变量的更多信息了。期望反映了一个随机变量整体值的大小，方差反映了值的分散程度。

为了好好试一试这两把武器，我们去挑战一下已经被我们战胜过几个小随机变量。

对于0-1分布$X \sim b(1,p)$：
$E(X) = 0\times(1 - p) + p = p$
$E(X^2) = 0\times(1 - p) + p$
$D(X) = E(X^2) - E^2(X) = p - p^2 = p(1 - p)$

对于二项分布$X \sim b(n, p)$，n次实验都是独立的
$E(X) = \sum_{i = 1}^{n}p = np$
$D(X) = \sum_{i = 1}^{n}p(1 - p) = np(1 - p)$

经过严密的计算后可以得知：
$X \sim \pi(\lambda), D(X) = E(X) = \lambda$
$X$为指数分布，则$E(X) = \theta, D(X) = \theta^2$

如果是$X \sim N(\mu, \sigma^2)$的正态分布，就更容易表示了。$E(X) = \mu, D(X) = \sigma$

我们讲了随机变量的这么多性质，最后还是和概率脱不了干系。如果一个随机变量的方差比较小，那么随便取一个数，这个数离平均值比较远的概率就会更小。严谨地说，通过方差的概念，有以下不等式，被称为切比雪夫不等式：

$P\{|X - \mu|>\epsilon\} \leq \frac{\sigma^2}{\epsilon^2}$

反着写也是一样的：

$P\{|X - \mu|\leq\epsilon\} \geq 1 - \frac{\sigma^2}{\epsilon^2}$

第三节 协方差与相关系数

上一节我们就注意到，$(E(XY) - E(X)E(Y))$这个式子不太对劲，它似乎和XY变量的独立性有关。把它做一些数学上的变换，可以得到$(E(XY) - E(X)E(Y)) = E((X - E(X))(Y - E(Y)))$，后面这个式子和方差的式子长得非常像。为了节约取名时间，人们把它叫做协方差，记为$Cov(X,Y)$。

协方差又有一堆性质：
(1)$Cov(aX,bY) = abCov(X,Y)$
(2)$Cov(X_1 + X_2, Y) = Cov(X_1, Y) + Cov(X_2, Y)$
同样，由观察很容易得知,$Cov(X,X) = D(X)$，一个随机变量和自己的协方差就是自己的方差。

协方差和独立性有关，但是不同数的协方差有大有小啊！独立性应该描述的是两个随机变量之间的关系，但我只要稍微乘一下其中一个变量，协方差的值就会改变(见性质1)。有没有一个专门用来表达和独立性有关的量呢？

可以发现,$0\leq \frac{Cov(X, Y)}{\sqrt{D(X)}\sqrt{D(Y)}}\leq 1$恒成立，那我们就用$\rho_{xy} =\frac{Cov(X, Y)}{\sqrt{D(X)}\sqrt{D(Y)}}$这个量好了！$\rho_{xy}$叫作相关系数。

两个随机变量独立，则相关系数为0；相关系数为0，但两个随机变量不一定独立。因为相关系数比独立性的范畴要小，它只反映了两个变量线性上的相关性。

第四节 矩、协方差矩阵

定义$E(X^k)$为k阶原点矩
定义$E((X - E(X))^k)$为k阶中心矩
定义$E((X - E(X))^k(Y - E(Y))^l)为$k+l阶混合中心矩

可以看到，期望是1阶原点矩，方差是2阶中心矩，协方差是2阶混合中心矩.

定义…………………………………………………………为协方差矩阵

说实话，这一小节就是一堆定义，而且只是原来某些定义的拓展而已。我暂时不知道这些东西算出来有什么用，老师上课时也是一笔带过。这一小节就过了吧。

本章总结

这一章我们学习了期望与方差——我们生活中评价随机变量的两个标准的严格数学定义。用了它们，我们就可以更好地生活，更好地判断赌博是亏了还是赚了，更好地在别人面前吹牛，可谓是一举多得。

本章的重点，一是方差和期望的计算。这个计算本质上就是一个简单的积分，可以看成是对一元简单积分的复习。二是期望和方差的一些运算性质。这些运算性质会在题目和后面的学习里被广泛用到。

第三章 多维随机变量及其分布

学微积分时，一般是先学一元微积分，再介绍多元函数，再介绍多元微积分。学习的重点还是二元微积分，因为学会从一元推广到二元，就能够再推广到多元。

多维随机变量的学习也是如此，教材也主要介绍了二维随机变量。在学多维随机变量的时候，很多概念和一维随机变量是类似的，我们关注的重点应该一维随机变量推广到多维随机变量的转化思想。

第一节 二维随机变量

这一节全部在讲一维随机变量的概念在二维中是什么样子的。其实只要理解二元函数和一元函数，这些概念就很容易对应过去。

分布律变成了描述$P\{X = x_i, Y = y_i\}$，画出来的表格应该是一个二维的表格：

概率密度函数则是一个二元函数$f(x,y)$

分布函数对于离散型变量，是一个双层求和；对于连续型变量，则是一个二重积分。

可以看出，所有概念的迁移都非常自然，我们快点进入下一小节。

第二节 边缘分布

某一天，我们兴冲冲地求出了一个二维连续型随机变量的概率密度函数，就比如上一章提到的打靶打中哪个位置。

突然，有个人把靶子重新画了一下。他把靶子涂上了斑马线一般的红白相间条纹，之后说：“现在，越靠中间的直线，分数越高。‘靶心’是中间那条红线。”

也就是说，现在我们不关心我们在靶子上的y轴打在哪个位置，只关心x轴打在哪个位置。我们现在需要求的是一个一维随机变量，但我们只有二维随机变量的概率密度函数啊！

这时候，可以很自然地想到，忽略y轴，就是y可以取任意值。不妨做积分$f_X(x) = \int_{-\infty}^{\infty}f(x,y)dy$。这样求出来的概率密度函数就只含x了。

边缘分布函数、边缘分布律、边缘概率密度等概念就是按照上述方法，把一个多维连续型随机变量去掉某维后，得到的结果。边缘分布函数就是直接把$\infty$代入式子，边缘分布律就是一行或者一列的数值求和，边缘密度就是求一个R上的广义积分。说实话，我感觉这个概念很容易理解，却又没看到什么实际应用，太无聊了。快进入下一小节吧。

第三节 条件分布

本节我们老师没讲，也不做为考试内容，但我还是稍微谈谈我的理解。

在第一章里，曾提到了条件概率。但那个时候我们只会用语言来描述一个随机事件。而现在的条件分布，是对一个随机变量求条件概率。理论上其中使用的方法是一样的。

本节并没有的新的内容，只是把第一章和第二章概念进行了一些排列组合。只要能看懂$F_{X|Y}\{x|y\}$的意思是$P\{x \leq X | y = Y\}$，就基本能搞懂本节。

第四节 相互独立的随机变量

和第一章一样，介绍了条件分布后，现在又开始介绍随机变量的独立性了。

还是和第一章类似的一个式子，若$F(x,y) = F_X(x)F_Y(y)$，则随机变量$X,Y$独立。

对于分布律和概率密度，也有类似形式的式子。

和之前一样，独立性就是一个十分简单的概念。给二维随机变量概率密度、分布律或分布函数，能判断两个变量是否独立，就算是学完了这一小节了。

第五节 两个随机变量的函数的分布

和第二章最后一小节一样，这一小节也是讲随机变量的函数的分布，只不过我们讨论的对象是两个随机变量。

虽然我们有两个变量，但本章讨论的函数只有一个值（或者说我们只有一个函数）。也就是说，两个变量$X,Y$经过函数变成了$Z$后，原来的二维随机变量就变成了一维的了。

本章的内容说是概率论的内容，但本质上是对一个概率密度函数的操作，内容实际上是二元微积分的内容。

$Z = X + Y$时，$f_{X+Y}(Z) = \int_{-\infty}^{\infty}f(x, z - x)dx$

$Z = XY$时,$f_{XY}(Z) = \int_{-\infty}^{\infty}\frac{1}{|x|}f(x, \frac{z}{x})dx$

$Z = Y/X$时,$f_{Y/X}(Z) = \int_{-\infty}^{\infty}|x|f(x, xz)dx$

其中$Z = X + Y, Z = XY$时，$x,y$是对称的，对应式子的x也可以被替换成y。

以下内容假设XY独立。

$Z = max\{X, Y\}$时，$F_Z(z) = P\{Z \leq z\} = P\{X\leq z\}P\{Y\leq z\} = F_X(x)F_Y(y)$

$Z = min\{X, Y\}$时，$F_Z(z) = P\{Z \geq z\} = P\{X\geq z\}P\{Y\geq z\} = 1-(1-F_X(x))(1-F_Y(y))$

对于这一节的题目，直接把条件代入公式，求积分即可。值得注意的是，上面的式子虽然是负无穷积到正无穷，但实际上很多积分在变量代换后是有一个上下界的。一定要画好图，搞清楚每个变量的取值范围，再写积分。求完结果最好全部把结果加一下，看和是否为1。

本章总结

这一章完全是对已学知识的应用、拓展。本章涉及了第二章一维随机变量的有关概念，并于第一节的条件概率、独立性结合，得到了条件分布、独立随机变量等概念。其中很多地方还需要用到微积分的知识。

仔细看来，这一章没什么新的内容。倒是多元微积分很久没用过了，可以借此机会复习一下。

第二章 随机变量及其分布

1.随机变量

在随机试验里，事件一般都是比较抽象的概念，比如从班上的学生中随机挑出三人，观察男女生的情况；在上课的某一时刻检查全体学生的行为，观察是否玩手机的情况。这些事件只能用文字描述，难以用数学的语言来描述。但我们常常关注的，是事件中的一些数字特征。比如，我们关心从三个人中几个人是男生，全班同学里几个人正在玩手机。这样的数字特征，就是随机变量。

用严格的话说，对于随机变量的每个基本事件（样本空间中的元素），你都可以用一个唯一的数字来代表它。这样一个从事件映射到数字的函数就是随机变量。函数的自变量是用文字或其它方式描述的情况，函数值是一个数。比如，设X(e)是随机挑三人，男生数的随机变量，那么X(男女男)=2。

随机变量的概念其实非常好理解，就是我们从每一个随机的结果中取一个数来。本小节仅仅介绍了随机变量的基本概念。后面的几小节、几章都是在介绍随机变量相关的性质、应用。

2.离散型随机变量 分布律

这一小节的标题很高大上，我们不妨先谈一些概率论以外的事情。

离散一词来源于集合论。当事物的数量上升到无穷多个时，它们之间的多少已经不能用普通的方法来评价了。自然数和整数谁多？整数还是实数多？从数量的角度来说，它们都是无穷多个。

因此数学家用函数映射的角度来表明无穷集合的多与少。如果一个集合可以映射到另一个集合，那说明这个集合肯定是不比另一个集合“小”的。如果两个无穷集合互相建立映射（双射），那么它们的大小就差不多，就是等势。

整数和自然数都有无穷多个，但它们都是可以一个一个可以数过去的。如果一些数的数量是有限个，或者有无限个但能和整数或自然数建立上述的双射关系，那么这些数就是离散的。

本节的标题就是在说，我们讨论的随机变量的值都是0，1，2，3，4这样可以一个一个写出来的。

由于我们的生活中接触的大部分量都是离散的，离散随机变量的例子十分多。上节提到的男生人数就属于离散型随机变量。像抽签、抽球、被车撞这种和个数有关的随机试验，都可以用离散随机变量来描述：抽没抽中、抽到几个一样颜色的球、一定时间地点里被车撞的人数。

为了表示这种随机变量的概率，人们用使用分布律来表达。分布律其实又是一个函数，把一个随机变量的值映射到了一个0~1的概率值上。这样的话，一个基本事件先被转换成随机变量的值，再被转换成了概率。随机变量成了一个求事件概率的中间媒介。

分布律一般写成表格：

人们发现，离散随机变量的原理很类似，也就是说，这些随机变量代表的函数的形式和类似。你只要改变函数的参数，就可以得到一个符合当前情况的函数。所以人们研究了一些常见的离散型随机变量。

0-1分布

抽签、中奖、表白，要么成功，要么失败。那么我们用0表示失败，1表示成功，用p表示该事情成功率。那么分布律是：

0-1分布的意义太容易理解了。

二项分布

这次没中奖怎么办？表白失败了怎么办？再试一次啊！

我们做很多次可能成功可能失败的事情，每次成功率固定，那么成功的次数这个随机变量就是二项分布。

如果设做一件事做了$n$次，那么所有长度为$n$，共$2^n$个01串就唯一代表了一种成功失败的情况。这种情况是基本事件。通过第一章古典概型的概念可知，一个事件的概率，等于其包含的所有基本事件除以总基本事件数。再运用一下排列组合知识，你就可以得到二项分布发分布律了：

也就是说，$P(X = k) = \tbinom{n}{k}(1 - p)^{n - k} p^k$

这个公式和二项式展开的系数完全一样，因此得名。从公式可以看出，二项分布有两个参数——事件次数n，成功概率p。二项分布记为$X \sim b(n,p)$

泊松分布

彩票还是不中怎么办？我决定每时每刻地都去买彩票，这样很快就能中奖了。

但是，这样是不可行的。第一，你没有那么多去买彩票，理论上你通过大量买彩票来中奖，你的投入都是比收获少的；第二不可能每时每刻都有彩票在卖。

不过，现实中还是有很多事是几乎在每时每刻发生的。比如，马路上车来车往，随时都有可能发生交通事故，尽管这个概率很小。

人们在数学上求出了这种无时不刻都在发生，也就是说事情次数无穷多情况下，某件事情成功次数的概率。这样的离散随机变量就是泊松分布。

设次数为$n$，成功率为$p$，令$\lambda = np$。在二项分布的公式，中代替掉p后，

$P(X = k) = \tbinom{n}{k}(1 - p)^{n - k} p^k = \tbinom{n}{k}(1 - \frac{\lambda}{n})^{n - k} (\frac{\lambda}{n})^k$，

再令$lim_{n->\infty}$，最终得出了一个奇特的式子:

$\begin{aligned}P(X = k) = \frac{\lambda^ke^{-\lambda}}{k!}\end{aligned}$

泊松分布只有一个参数$\lambda$,记为$X \sim \pi(\lambda)$。

在现实生活中，尽管事情不可能发生无穷多次，但只要这个发生次数n很大时，我们就可以用泊松分布的公式来近似代替二项分布的公式，以减少计算量。

3.随机变量分布函数

有了随机变量，我们已经可以求出很多有用的信息了。比如，掷硬币10次，正面朝上的次数为0~10次中某次的概率。但是，有些人还是不满足：幸运女神告诉我，今天我去掷10次硬币，如果正面朝上的次数是4~6次，我就会很幸运。我今天幸运的概率有多大呢？

你当然可以把随机变量为4、5、6的概率加起来，但这样计算总感觉不太对劲。试想一下，如果不是掷10枚硬币，而是掷10000枚硬币，求正面朝上4444~6666的次数的概率，那计算起来会非常慢。或者我们处理的是非离散的随机变量，每一个点的概率都是0，我们甚至无法累加它们。

总结一下，生活中，我们常常关心的是随机变量落在一个区间的概率。累加每一个离散型随机变量的概率可以解决的这个问题，但运算效率较低；而非离散随机变量无法累加。为了能求出所有类型的随机变量的区间的概率，我们必须得用一些其它的方法。

我们先在离散型随机变量中找出一种方法。在数学（或者说计算机科学）上，有一种快速求某个区间和的方法：求前缀和。也是说，对于随机变量的每一个值，求第一个值到这个值的和。前缀和$F(x) = \sum_{i = 1}^{x_i}P\{X = x_i\}$，其中$x_i$为第一个小于等于$x$的随机变量的概率。观察一下可发现，$F(x) = P\{X \leq x_i\}$。那么对于任意某个区间$(a, b]$的概率$P\{a < X \leq b\}$，其值就等于$F(b) - F(a)$。

这个反映了随机变量分布情况的函数$F(X)$就叫做分布函数。

4.连续型随机变量 概率密度

离散的反义词是连续，所以肯定还有连续型的随机变量。连续型随机变量每个值的概率都为0，所以我们无法用分布律来描述它们。不过，连续型随机变量区间的概率是有意义的，而上一节我们正好有了一个描述区间概率的工具——分布函数。连续型函数可以通过分布律来定义。

在离散的情况下，我们用的是求和；在连续情况下，我们就应该用积分。若随机变量$F(x) = \int_{-\infty}^{x}f(t)dt$，则$F(X)$是连续性随机变量，$f(t)$是概率密度。离散型随机变量中求和的是分布律，连续型随机变量中积分的是概率密度。也就是说，概率密度就对应着分布律。若要描述一个连续型随机变量，我们只要描述它的概率密度就行了。

和离散型类似，许多连续型随机变量的函数都有同样的形式。例如：

均匀分布

我随意地往靶子上射了一枪，保证不射到靶子外面。

对于靶子这个面，我射中每一个点的概率都是等可能的。如果靶心画得大一点，我射中靶心的概率就大一点。

如果随机变量每个值的概率都相等，也就是对于概率密度$f(x)$：

$$f(x) = \left\{ \begin{aligned} &\frac{1}{b - a} &x \in (a,b] \\ \\ &0 &else \end{aligned} \right.$$

记为 $X\sim U(a, b)$

指数分布

我没有深刻理解指数分布的实际意义，只给出它的概率密度$f(x)$：

$$f(x) = \left\{ \begin{aligned} &\frac{1}{\theta}e^{-x/\theta} &x > 0 \\ \\ &0 &else \end{aligned} \right.$$

由于指数函数的性质，指数分布有无记忆型。若符合指数分布的随机变量X为灯泡寿命，则X正常运行t小时的概率，等于运行了s小时后，再运行t小时的概率。

正态分布

世界上，极强与极差的人都是少数。我们大多数人只不过是泛泛之辈，和他人并没有什么两样。

当对于一个很大的群体进行调查时，能够发现，无论是身高，还是体重，还是其它一些可以用数字描述的特征，都满足上述的性质：大部分人都处于中间水平，越是偏离中间水平的样本，数量就越少。

这样的随机变量满足一个神奇的分布——正态分布，其概率密度$f(x)$:

$f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x - \mu)^2}{2\sigma^2}}$

这个函数有两个参数$\mu,\sigma$。记为$X \sim N(\mu, \sigma^2)$。（注意后面的平方）

这个式子非常不好记，但从某个角度可以更好地理解这个式子。

我们知道，整个样本空间的概率为1，也就是概率密度在R上的积分为1。那么对于正态分布函数：

$$\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x - \mu)^2}{2\sigma^2}}dx = 1$$

做变量代换后：

$$\begin{aligned} &\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x - \mu)^2}{2\sigma^2}}dx \\ &=\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x - \mu}{\sigma})^2}d\frac{(x - \mu)}{\sigma} \\ &=\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}t^2}dt \end{aligned}$$

右边那个$\int_{-\infty}^{\infty}e^{-\frac{1}{2}t^2}dt$积分积出来就是${\sqrt{2\pi}}$，这是一道多元微积分例题。

把$\frac{x - \mu}{\sigma}$看成一个整体的话，整个式子就好记多了。事实上，$\phi(x) =\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}$就是标准正态分布的概率密度。其分布函数$\Phi(x)$的值人们已经算好了。求某个正态分布的有关量时，可以先做$\frac{x - \mu}{\sigma} = x$变量代换，在标准正态分布的情况下讨论。

求所有连续型随机变量的概率和离散型的方法是一样的。先通过概率分布（之前是分布律）积分得到分布函数，再在分布函数上做差，就可以得到某一区间的概率了。

5.随机变量的函数的分布

这一章里面我们已经提出了很多奇奇怪怪的要求了。我们先是要求把一个随机事件用一个数表示，然后又要求出随机变量为某个值时的概率，再要求求出随机变量在一段区间里的概率。

在这一节里，我们提出了最后一个需求：求出一个随机变量的函数的分布。比如设$X$为班上随机挑3个人中男生个数的随机变量，我突发奇想，要求出$Y = X^2$这个随机变量的分布。

这个需求很难找到一些比较有实际意义的例子，我暂且把他当成一种数学运算技巧。

计算随机变量函数的分布也很简单，直接无脑地按照定义往式子里套就行了。

例题：
$设X的概率密度为f_X(x)，求Y = X^2的概率密度$
解：

$$\begin{aligned} F_Y(y) &= P\{Y \leq y\} = P(X^2 \leq y) \\ &= P(-\sqrt{y} < X \leq \sqrt{y}) \\ &= F_X(\sqrt{y}) - F_X(-\sqrt{y}) \\ \\ f_Y(y) &= \frac{dF_Y(y)}{dy} \\ &= \frac{F_X'(\sqrt{y}) + F_X'(-\sqrt{y})}{2\sqrt{y}} &(y \geq 0) \\ f_Y(y) &= 0 \ &else \end{aligned}$$

在这里在特别提醒一下，所有求概率密度、概率分布函数的题目，要考虑到定义域，要把所有定义域下的函数值都写出来。有的式子推式子推得很爽，但忘记了没有定义域的地方，比如上题中的$y < 0$

多做几个题就能发现，对于单调函数，可以直接得到新的分布。设$h(y) = x$是原随机变量函数的反函数，则$f_Y(y) = f_X[h(y)]|h’(y)|$。但对于非单调函数，比如上面的$Y = X^2$，只能老老实实地计算了。

本章总结

本章一开始，我们从用自然语言或其它方式描述的随机事件中，提取出一个数来，把这种从基本事件到数的映射称为随机变量。围绕着随机变量，我们探讨了离散和连续的情况下，常见的随机变量有哪些，随机变量的概率应该怎么求，随机变量的函数的概率该怎么求。

应该可以说，这一章是整个概率论的基础。后续的很多内容都建立在本章内容之上讨论。

为了尽快复习，我会尽可能把内容精简一些，不会像第一章那样放那么多例题了。很快我就得考试了，除了复习理论外，我还得多做一些题目。