The following is based on solutions provided by the problem setters.

以下内容以出题人提供的解答为基础。

Problem A: **Who Gets the Most Candies?**

This problem is a variant of the Josephus problem which can be solved with segment tree. Let *P* be the largest antiprime not exceeding *N*. The *P*-th child jumping out of the circle is the answer. Distribution of antiprimes is sparse. All antiprimes required for this problem can be computed in advance and hard-coded into the source.

这个问题是约瑟夫问题的一个变种，可以用线段树解决。如果不超过*N*的最大反素数是*P*，那么第*P*个出圈的孩子就是答案。反素数的分布很稀疏。这个题目用到的全部反素数可以提前计算出来直接写到源代码中。

Problem B: **Big String**

There is an algorithm whose running time does not rely on the length of the initial string. Consider the inserted characters to be inserted into gaps between successive characters of the initial string. Before each insertion, keep all previous insertions in a table ordered by their positions. To insert a character before *p*-th character of the current string, start from the *p*-th character of the initial string and walk backward to find the right position for insertion, which can be found in at most *N* steps. Queries can be processed in a similar way. This algorithm runs in time *O*(*N*^{2}).

可以设计出不依赖于原始字符串长度的算法。把每个插入的字符看作被插入到初始字符串的相邻字符之间的空隙中。每次插入前，把之前插入的所有字符按顺序保存在一张表中。要在第*p*个字符之前插入一个字符，只需从初始字符串的第*p*个字符开始向前寻找，最多回退*N*步就可找到合适的插入位置。查询可以用类似方法处理。算法的时间复杂度是*O*(*N*^{2})。

Problem C: **Bracelet**

This is a constrained orbit-counting problem where Burnside’s lemma applies. The constraints can be represented by a directed graph. There is a edge from vertex *i* to vertex *j* if and only if beads of kind *i* and kind *j* can be stringed next to each other. Let *A* be the adjacency matrix. Then the answer is given by the expression below.

这是个有约束的轨道计数问题，可以应用Burnside引理解决。约束可以用一个有向图来表示。从顶点*i*到顶点*j*有一条边当且仅当种类*i*和种类*j*的珠子可以相邻。记邻接矩阵为*A*，则答案由上面的式子给出。

Problem D: **Unique Solution**

This problem is to determine whether there exists a unique set of *M* non-overlapping segments of consecutive elements of a sequence of *N* integers such that the sum of elements it covers is maximum. The algorithm is based on dynamic programming and recursion. First, use dynamic programming to build an *M* by *N* table of which the element in the *i*-th row and the *j*-th column is the maximum sum under the condition that the problem is limited to *i* segments on the first *j* elements and the *j*-th element is covered. Second, enumerate all possible last segments in the optimal set and use recursion to determine whether the set is unique.

确定一个*N*个元素的整数序列的最大*M*段和是否有唯一解。算法基于动态规划和递归。首先，用动态规划求出一张表。第*i*行第*j*列的元素表示前*i*个整数的最大*j*段和的最优解。然后，枚举最优解中的最后一段，用递归确定最优解是否唯一。

Problem E: **Matrix Multiplication**

Matrix multiplication won’t do for this problem. The given matrix *A* can be regarded as the adjacency matrix of a directed graph. Since all elements on the primary diagonal are 1’s and the dimensions are less than 2006, the graph with *A*^{2006} as its adjacency matrix is the transitive closure of the graph represented by *A*. The number of elements that are 1’s is equal to the number of ordered pairs of vertices (*i*, *j*) such that there exists from vertex *i* to vertex *j*.

矩阵乘法不能解决这个题目。给出的矩阵*A*可以看作一个有向图的邻接矩阵。由于主对角线上的元素都是1，而且矩阵的阶小于2006，所以为*A*^{2006}邻接矩阵的图就是由*A*表示的图的传递闭包。*A*^{2006}中为1的元素个数就是所有从顶点*i*到顶点*j*存在一条路径的有序顶点对(*i*, *j*)的数目。

Problem F: **Strange Way to Express Integers**

Suppose *C* ≡ *A*_{1} (mod *B*_{1}) and *C* ≡ *A*_{2} (mod *B*_{2}). Let *C* = *A*_{1} + *X*_{1}*B*_{1}, we get *X*_{1}*B*_{1} ≡ *A*_{2} − *A*_{1} (mod *B*_{2}). Find *X*_{1} using the extended Euclidean algorithm and thus find *C*. Let *B* = *lcm*(*B*_{1}, *B*_{2}), then the two equations above can be replaced by *C*’ ≡ *C* (mod B). Iterate until there is only one equation.

假设*C* ≡ *A*_{1} (mod *B*_{1})，*C* ≡ *A*_{2} (mod *B*_{2})。令*C* = *A*_{1} + *X*_{1}*B*，那么*X*_{1}*B*_{1} ≡ *A*_{2} − *A*_{1} (mod *B*_{2})。用扩展欧几里德算法求出*X*_{1}，也就求出*C*。令*B* = *lcm*(*B*_{1}, *B*_{2})，那么上面两条方程就可以被*C*’ ≡ *C* (mod B)代替。迭代直到只剩下一条方程。

Problem G: **Tunnel Warfare**

Denote the unattacked or rebuilt villages with 0 and destroyed villages with 1, then the problem is reduced to finding the first 1’s to the left and to the right of some element in a string of 0’s and 1’s. Using a binary search tree or dividing the string into segments as long as the square root of the length of the string will solve the problem. Taking advantage of the condition that reconstruction was done in the reverse order of destruction, using a binary indexed tree will also do.

用0表示没有受到攻击或者已经重建的村庄，用1表示被摧毁的村庄，那么问题就规约为寻找一个01序列中某个元素左边和右边的第一个1。用一个二叉搜索树或者将串切分成长度的平方根那么长的小段都可以解决这个问题。利用按摧毁的逆序重建的条件，用树状数组也可以解决这个问题。

Problem H: **M × N Puzzle**

If *N* is even, transpose the puzzle. Write down the numbers on the tiles in both the starting and goal states (0 for the missing tile) in row-major order to form two sequences of integers. Let *I*_{1} and *I*_{2} be the numbers of inversions of the sequences and D be the Manhattan distance from the position of the missing tile in the starting state to that in the goal state. The puzzle is solvable if and only if *I*_{1} + *I*_{2} + *D* is even.

如果*N*是偶数，交换行列。将初始状态和目标状态的木块上的数字按行优先顺序写下来变成两个整数序列。令*I*_{1}和*I*_{2}为它们的逆序数，*D*为空位在初始状态和目标状态中位置的曼哈顿距离。游戏可解当且仅当*I*_{1} + *I*_{2} + *D*为偶数。