A 圆圈游戏
一道优秀的扫描线题。
我们考虑没有相交和包含，提示我们可以通过包含的关系建立出一棵树，一个点的儿子就是它极大的包含的圆。
如果能够建立出这个树，那么我们可以在树上做一个非常 trival 的 $dp$ 解决问题。转移就是枚举选不选这个点。
我们考虑怎么建立这个树。考虑从左往右进行扫描，到达一个圆的左端点的时候就加入这个圆，到达右端点的时候删掉他。我们考虑在删掉一个圆的时候找出它的父亲。
如果这个圆右端点向上引一条切线，考虑讨论一下这个切线碰到的第一段弧。如果这段弧是一个上圆弧，显然我们找到了它的父亲，就是这个上圆弧对应的圆。如果碰到了一个下圆弧，那么这个点一定和碰到的下圆弧这个圆是兄弟关系，也就是它们的父亲相同。因为画一下会发现，此时不可能存在一个圆单独包含这个圆或者碰到的那个圆，如果存在，碰到的就不会是那个圆了。
那么还有一个问题，怎么维护这些圆呢？不难发现，随着扫描线的移动，圆之间的相对关系一定不会改变。因此直接把这些圆弧拖进一个 set 中维护即可。
代码实现上有一个需要注意的地方，插入和删除圆弧的时候一定要用当前的 $x$ 对应的 $y$ 来比较，直接比较最左端点或者最优端点的 $y$ 显然是不对的。
复杂度 $O(n\log n)$ 。
B 划分序列
结论题。我场上打表打出了最小值关于 $k$ 的单峰关系，却没看出这个结论。。。
我们先二分一个最大段的最小值，于是问题就变成了能否选择恰好 $k$ 个段使得每个段的和都小于等于 $mid$ 。如果打一个表会发现，最后答案关于 $k$ 是一个单峰函数，也就是说，如果确定了 $mid$ 的值，合法的 $k$ 一定是一段区间。（场上没看出这两个条件等价感觉非常亏）
于是剩下的部分就非常简单了，我们考虑求出最小的合法的 $k$ 和最大的合法的 $k$ 。也就是求出此时最少选择的段数和最多选择的段数，转移非常显然，就是
这个问题只需要对前缀和离散化一下就变成了后缀最大最小值查询，一个 BIT 即可搞定。
C 生成树求和
这个题我是做过一个几乎一样的题的，场上数组开小了 TAT
有一种并不需要单位根但是仍然可以通过的做法，虽然比单位根多一个 $n$ ，但是 $O(n^4\log v)$ 是非常稳的。
显然这个题可以逐位考虑。然后我们对于每条 $0$ 边，认为它边权是 $1$ ，对于每条 $1$ 边，认为边权是 $x$ ，$2$ 边边权是 $x^2$ 。然后我们考虑用矩阵树定理求出所有生成树的和，不难发现求出来的东西是一个关于 $x$ 的多项式，这个多项式的 $x^i$ 系数就是加起来等于 $i$ 的生成树个数。
但是显然直接对这个东西做高斯消元很不行。但是最终多项式系数不超过 $2n$ （就是这个东西，我把数组开到 $n$ 于是炸了），所以可以插值一下，求出 $i = 1\dots 2n$ 的时候 $f(i)$ 的值，这里每个值都可以一次矩阵树定理计算。最后直接拉格朗日插值即可。
复杂度是 $O(n^4 \log n)$ 。
这个做法显然不如用单位根优秀，但是它可以求出在固定选择 $i$ 条 $1$ 边和 $j$ 条 $2$ 边时的答案。
再写一下单位根的做法。由于 $10^9 + 7$ 为模数的时候是不存在三次单位根的，我们可以扩域，把每个数写成 $a + b\omega_3$ 的形式。由于 $\omega_3^2 = -\omega_3$ ，每条边的边权就是 $1$ ，$\omega_3$ ，$-\omega_3$ 。然后直接对这个东西做矩阵树定理即可。求逆元的时候用共轭复数推一下就有了。
复杂度是 $O(n^3\log n)$ 。