（进度： 9 / 10
Brief description:
Problem A. Addition chains:
[加法链][大数][构造]
构造 n 的加法链、长度越短得分越高、长度不得超过 500。
（n ≤ 10^100 ）
Problem B. My Fair Coins:
[线性递推数列][类斐波那契数列][矩阵乘法]
略）
Problem C. Dynamic GCD:
[轻重边树链剖分][线段树]
给定一颗树，动态维护以下操作:
- C u v d: 每次一条路径上的数 + d。（d 为正数）
- F u v: 求一条路径上所有数的 gcd。
Problem D. Chef’s Dream:
略.. O(nlogn) 贪心)
Problem E. Equivalent Suffix Tries:
给定一个串 S、问有多少串的 Suffix Tries 与其同构。
Problem F. Favourite Numbers:
[自动机DP][数位DP]
给定一组病毒串，问 [l, r] 区间内，第 kth 个包含有病毒串的数是多少。
Problem G. The Gray-Similar Code:
[nice][adhoc]
给定一个长度为 n 的序列 {ai}，相邻两个数之间的 xor 相差一位。
问数组中是否存在一组 1 ≤ i1 < i2 < i3 < i4 ≤ n, 使得 a_i1 xor a_i2 xor a_i3 xor a_i4 = 0。
Problem H. Little Elephant and Bubble Sort:
[概率][树状数组]
一个数组，对于每一位有 pi 的概率为 ai, 1-pi 的概率为 bi。。
问该数组执行冒泡排序的期望交换次数。
Problem I. Restaurant Rating:
[动态维护第 k 大数][大根堆 + 小根堆][平衡树 TLE?]
动态维护一个序列，要求支持以下操作：
1 x: 插入一个数 x。
2: 询问第 kth 大的数，k 为 \floor{n/3}。。。
Problem J. Gift Rift:
[签到题][鞍点]
略）
...
Analysis:
Addition chains:
有待补完）
Dynamic GCD:
目测不能上动态树（？。。。
。。。那么树链剖分是常规了。。集中分析单链的情况怎么维护。。
分析修改操作。。那么一段数 +d 的话。。。相对之间的差是不变的。。
然后注意 gcd 的性质。。 gcd(a, b) = gcd(a – b, b);
那么一串数的 gcd 可以转换为。。gcd(a, b-a, c-a, d-a … )
（参见 GCJ Qualification Round 2010 Problem B. Fair Warning
这样就可以用块状链表来维护。。。对于块状链表的大小。。
这里有两种选择。。一种是对所有链用一个统一的值 （例如 整颗树的 sqrt(n) 。。
另一种是对每条链用不同的值。。（每条链的 sqrt(n)。。。
这里有待分析。。。
但是以上两种方法都 TLE 了。。。
下面退回前面一个步骤。。。
仍然是利用那个兴致。。。注意到一串数的 gcd 可以转换为
gcd(a, b-a, c-b, d-a) 。。。。。
这样再对原数列差分得到数列 b。。。修改操作的话。。至多只会影响到 b 数组的两项。。。
于是成段修改（+d）成段询问的 gcd 。。。就等价于求以下两个子问题的 gcd。。。。。
成段修改 (+d)，单点询问。。。
单点修改，成段 gcd。。。。
以上两个问题分别用线段树维护即可。。
Equivalent Suffix Tries:
。。。
Favourite Numbers:
dp[i][u] 表示当前长度为 i，在自动机的 u 位置时有串是存活的。。
因为串都是反着 Input 的，所以状态转移的时候注意向相反方向转移。
数位DP好像也可以但是好像不怎么好写。。）
The Gray-Similar Code:
假设存在一组解，i1, i2, i3, i4。
则设 Ai1 ^ Ai2 = Ai3 ^ Ai4 = mask;
。。若 mask != 0 ，则必存在相邻两项属于 [i1, i2] 和 [i3, i4] 区间，使得它们的 ^ 等于 mask 中的一个二进制位。
（从路径的角度考虑即可。。）
这样整个算法就分成了两个步骤，首先先判断 mask = 0 的情况，这种情况有两类。（4个一样的数，或者2组2个一样的数。）
之后处理 mask != 0 的情况，做差分预处理出一个 int S[64]; 的数组扫描即可。注意使用 unsigned long long;
…
