。水题略。。）
Sereja and Data Structures
Brief description:
。。给定长度为 n 的数列 {an}。。记 s(l, r) 为 [l, r] 区间里最大数与最小数的差。。。
。。。询问所有 s(l, r) 的的积。。（。。数据保证是随机生成的。。。
Analysis:
。。分治。。每次找到当前区间的最大值记作 m（。。或最小值。。可以比较哪一个更接近中点。。
。则按从小到大的顺序插入其他数字。。（。这一步暴力排序。。
。。。。左右各维护当前最远的可用距离。。。复杂度 O(nlog^2n)
。（Remark：和 N 年前我出的一个题 一样。。依赖于数据的随机性。。不过这个题的 Killer 似乎很好构造？。。给个递增的数列就行了。。
Arigeom Beats
Brief description:
。给定 n 个正整数 {An}，将这些数分解成一个 AP（算数序列） 和一个 GP （几何数列）。。。
允许一个数同时出现在 AP 和 GP 中。。。 p 可以是有理数。。（记 d 为 该 AP 的公差。。p 为该 GP 数列的公比。。下同。。
（。。{An} 递增给出且互不相同。。。。n <= 1e4, Ai <= 1e5 ... 。。)
Analysis:
（。。。做法类似 CF 这题。。
。。
由于每项至少存在在 AP 和 GP 中的一个。。。
。。考察前 3 个数。。必然有 2 个会落在 AP 或者 GP 中。。且是该数列中最小的两项（外层共需枚举 6 种情况。。
。。。。。那么 Sub Task 是验证是否存在一个 AP （或者 GP 数列）。。使得。。某些数字必须出现。。某些数字可以出现。。
- 对于 AP。。。
- 对于 GP。。。
。。如果存在，则对所有必须出现的数字排序。。d 一定是所有相邻数字的差的 gcd 。。。
。。如果存在，则对所有必须出现的数字排序。。则 最小数 和 最大数 必然可以是 GP 数列的第一项和最后一项。。
设最大数 / 最小数的最简分数为 A / B 。。GP 数列有 m+1 项。。那么 a 和 b 的 m 次方根都必须是有理数。。。
。。即合法的 m 为 。。。 A 和 B 的所有质因子的幂的 gcd 的约数。。。。
Different Trips
Brief description:
。。给定一颗有根树。。问所有根到叶子结点所构成的字符串集合。有多少不同的子串。。。
。结点所表示字符等于这个结点的度数。。
Analysis:
。。开始一直从动态添加字符的角度考察这个问题。。（。。呵呵呵。。
。后来在著名图论巅峰人物 Daizhenyang 的注视下终于认识到了我的弱菜本质。。。
。其实把根到每个结点的路径。。组织成一颗静态的后缀数组就行了。。。
。。要对倍增算法进行少量的 Modification。。。（。。使用倍增祖先。。其他全部类比原算法即可。艹？。。这似乎是个经典的题啊？
。。按照叶子到根结点的顺序计算 height 数组的。。以保证线性复杂度。。
1. 遇到已经计算过的。。则直接 break 掉；
2. 若某时刻 u, v 相同。。则直接 height += dep[u]； break 掉。。
(Remark: http://www.lydsy.com/JudgeOnline/problem.php?id=1921
Quasi-Polynomial Sum:
.. 这个题需要用到。二项式定理 (Binomial theorem)。。霍纳规则(Horner’s method)。扩展欧几里德算法(Extended Euclid’s algorithm)。。数论变换(Number-theoretic transform)。。快速傅里叶变换(Fast Fourier transform)。和中国剩余定理(Chinese remainder theorem)
。。。这个题超出了本菜的能力范围。。。（呵呵呵呵。。。
。。。（题解 看都看不懂我会乱说？。。 。。
WordNinjas:
。。。考虑到最后附加题本菜的算法非常弱智。。就不和大家分享了。！！。。
由于我没能把拟多项式和给撸出来。。最终还是傻逼的滚出了第一版主要还是自己弱也没什么好难过的。
。。（。。啥时候我才能像戴牛那样虐爆全世界呢？。。。 ）。。。
