**以下解答主要来自出题者提供的解题报告（可能略有改动）。由于本人能力的限制，可能对于很多数据结构和算法的理解存在偏差（如果发现什么问题，十之八九不是出题者的问题，而是我自己的理解有问题，因此写得不对），欢迎大家指正。:)

有的出题人提供的解题报告是英文的，但是很好理解，这里就没有翻译。

Happy 2006

对于所给的m，求出m的欧拉函数值v，我们知道1 ~ m之间与m互素的数的个数为v。于是m + 1 ~ 2m, 2m + 1 ~ 3m, 3m + 1 ~ 4m…….等区间均包含v个与m互质的整数。所以k / v即可以得到一共需要多少个这样的区间。然后在最后一个区间内枚举即可以确定要求的数。算法复杂度为O(m).

Long Long Message

Please forgot the dynamic programming algorithm for it. The standard algorithm is completely different. Construct a suffix tree for the first string (construct those failure links correctly). Then just traverse the second string on that tree. One may also use suffix array instead.
"Dedicate this problem to all the great mothers in the world."

The Number of the Same BST

假设树中总的节点数是n，以每一个节点为根的子树中包含的节点个数分别是sum[1], sum[2], ..., sum[n]。则不同BST的个数是n!/(sum[1] * sum[2] * ... * sum[n])。

因为要对9901取模，而9901是质数，因此可以不用写高精度。如果要求a / x，而且已知(x * y) = 1 (mod 9901)，那么a / x = a * y (mod 9901)。这里y可以用解同余方程的方法求得。

Cheat at Math

We suggest the incremental approach. Add one arc each time; then calculate the intersections of it and the existing arcs. Those intersections divide the current arc into some sections. We should add those sections one by one. With disjoint-set technique, adding one sections take only O(1). Hence, we shall have everything done in O(N^2logN) time.

Count Color

此问题主要考察的是线段树，同时结合二进制集合表示解决问题。

DNA Sequence

根据给定的非法DNA串,可以构造成出一个状态转化图，图中每个顶点表示一种状态，如对于一个DNA串ATC。则可以得到四个点的图,分别表示DNA序列尾部最多匹配了0个字符,1个字符,2个字符,3个字符。

图中有一个起始结点,表示什么都没匹配,沿着这个结点往后走n步,就得到一个长为n的DNA串,如果这个路径中没有经过不合法的顶点,那么这个DNA串就是合格的。上例中匹配了3个字符的定点就是不合法的顶点，它已经包含了ATC。

那么问题就是求出从初始节点出发不经过非法节点的长度为n的路径的条数，这个可以将图转化为矩阵，然后二分求解就可以了。

Atom Bombs! God!

我的算法是n^2logn+n^2的，n^2logn实际是排序很快，但是n^2的常数项有点大。对于这道题目，首先确信一些事情，就是对给定的点比如A和B，他们连接的直线与x轴的交点，算一个“事件”，在这个“事件”的地方，A和B的位置在最终的可是单词中会发生变化！

注意那些相同时刻的事件，一定要确定好先后顺序，比如1 2 3共线，当我们通过1 2 3所在的直线和x轴的交点的时候，我们需要将1/2, 1/3, 2/3都经过交换，比如：

1 2 3 swap(1,2)
2 1 3 swap(1,3)
2 3 1 swap(2,3)
3 2 1
成功！

1 2 3 swap(1,2)
2 1 3 swap(2,3)
3 1 2 swap(1,3)
1 3 2
失败！

如果我们按照这样的swap顺序，将无法得到正确的3 2 1。
因此我们要注意在事件的发生时刻相同时（就是x轴的交点相同时），要按照事件的内容进行排序（第二关键字）

Linearity

这是一道简单的几何计数题.即求给定点集中共线点的最大数目。可以有枚举加判定的办法，做到O(N^3)，显然不太理想。可以每个点为起点，做出向量，然后对向量按极角排序，最后判定的办法，排序用NlogN，有N个点，复杂度为O(N^2logN),有所改进，但是排序需要费一番周折。与第二种方法相同，对每个点，我们做出以该点为起点的向量(a, d)，因为我们关心的是向量的方向，与大小无关，所以我们将向量化成最简形式，即a,d同时除以其最大公约数，并在a小于0的时候，a,d同时反号。此时的(a, d)即唯一标识了一条直线。我们只需要用一个hash表甚至二维数组记录一下数对(a,d)出现的次数即可以得到对应的直线经过的点数，计数过程中记录最大值即可。整个算法复杂度为O(N^2)。