A

容易证明 ，所以一定每个数单独一段最优。

输出所有数的和即可。

B

可以发现删数一定是从小往大删的。

设最后一个被删的数是 ，则需要满足剩下的小于 的数不超过 个。

枚举剩下的集合还剩 个元素，则需要将 个删除的元素插入到留下的第 个元素之前。那么能插的空位一共有 个。使用组合数计算答案即可。

C

把式子看做平面上有 个点 ，需要找一个点使得到其它点的切比雪夫距离之和最小。

我们使用将切比雪夫距离转成曼哈顿距离的方法，将每个点 变成 ，然后两点间的切比雪夫距离就变成了两点间的曼哈顿距离的一半。这样两维就可以独立考虑，将答案相加。接下来以第一维为例。

我们要数轴上找一个点，满足其到 个点距离之和最小。容易证明可以选择从小到大第 个数。我们二分一下这个数的大小，然后 two pointers 扫一下求出小于这个值的数的个数。这样就能确定第 个数。

求出了这个数后，我们同样可以使用 two pointers 求出所有点到这个点的距离和。这样就解决了一维的问题。

对两位都用以上方法做一遍，就可以在 的复杂度内解决此题。

D

我们对于数组 的一位 ，写出它的 egf。

假设涉及到 的操作总共有 个，其中有 个是将其赋值为 的。则最后一次操作的方案有 种，而最后一次操作之前的每次操作的方案有 种。

那么生成函数就是 。如果初始 ，还要再加上 。

我们将每一位的生成函数分治乘起来，并且以 的形式维护多项式。容易发现这样的形式的乘法和普通多项式的乘法的规则一样。而由于 ，最终得到的多项式是 项的。

最后统计答案，对于每一项 ，我们求出 项的系数乘上 ，即 ，再将这些系数相加即可。

这样就在 的复杂度内解决了此题。

E

当一个小球沿着一条线段走完之后，其后的路线仅与这一条线段有关，而可以忽略小球原先的信息。这启发我们建立线段与线段之间的转移关系：当一个球从这条线段的下端点出发，我们想知道是否会遇到下一条线段，下一条线段是哪条，以及是否会在下一条线段上停止。如果不会停止，视为两条线段间的一条有向边。这个关系形成了一个森林的结构。

问题转化为给定一些坐标，问从这些坐标出发的每个小球是否会遇到一条线段，是哪条，以及是否会在下一条线段上停止。容易发现每个询问小球遇到第一条线段前的情况也是这个问题的模式，可以一起进行处理。

将问题分为两部分，第一步求遇到的线段可以将两种斜率的线段分别计算，转换坐标把线段变成水平的，离线扫描线即可。第二步求是否会在线段上停止，旋转平面把线段变成竖直和水平的，同样也是离线扫描线。总复杂度 。

F

我们把每个矩阵看做一个三个点的有向图，矩阵中 的权值表示 到 的路径条数。那么我们就是要在每张无向图中选择一条边，再选择一个排列，使得按照这个排列，这些边恰好构成一条从 号点出发的回路。即在每张无向图中选择一条边后，答案要乘上这张图的欧拉回路个数。

对于欧拉回路计数，我们有 定理，即：

• 若存在一个点入度不等于出度，则答案为 。
• 否则设 为该有向图的外向树个数，答案为 。

而在这题中，我们要求的欧拉回路并不要求 号点的第一条出边必须固定，那么答案需要再乘上 。

那么我们要求的答案就是对于每张图选择一条边，满足所有点的入度和出度相等，再在选出的边中选择一个边集构成一棵外向树，然后再乘上 。

那么我们可以 dp，定义 ，为前 张图， 号点的入度和出度为 和 ， 号点的入度和出度为 和 ，且选出的的一个边集为 的方案数。

这样就可以在 的复杂度内解决此题。

接下来提供一些本题的细节：

• 可以发现本质不同的 只有 种，而转移有 种边。所以这题常数要乘上 ，有较大常数。可以预先将转移的 的表处理出来减小常数和代码量。

• 欧拉回路中存在和 号点不连通的孤立点是合法的，最后统计答案时应考虑到这种情况。