注意，本篇文章均为嘴巴，无任何可信度。

km

稍微化简一下。

限制：

\[2[(x_i-x_j)(u_i-u_j)+(y_i-y_j)(v_i-v_j)] \ge -[(u_i-u_j)^2+(v_i-v_j)^2] \]

最大化：

\[\sum_{i,j} 2[(x_i-x_j)(u_i-u_j)+(y_i-y_j)(v_i-v_j)] \]

~~有某D姓选手一眼线性规划对偶，我特此来警（jue）示（mu）后（bian）人（shi）~~。

稍微推一下，发现这个等价于求：

\[\max \sum_i x_iu_i+y_iv_i \]

现在最难的还是这个限制。现在我们来证明存在一种满足限制的方案，使其顶到最大值。

反证，假设取到最大时，存在 \(2[(x_i-x_j)(u_i-u_j)+(y_i-y_j)(v_i-v_j)] < -[(u_i-u_j)^2+(v_i-v_j)^2]\)

注意到右边的东西小于等于 \(0\)。放缩一下，即有 \((x_i-x_j)(u_i-u_j)+(y_i-y_j)(v_i-v_j)<0\)。

移项得：

\[x_iu_i+y_iv_i+x_ju_j+y_jv_j < x_iu_j+y_iv_j+x_ju_i+y_jv_i \]

矛盾，以此得证。

剩下的部分随便做做就行了。

「2020-2021集训队作业」如果会出题就好了

如果会做题就更好了。

一棵树，两种操作，一种换根，一种求链上 \(len_u\) 的异或和。

其实很明显可以离线下来对吧。仔细思考换根对树上 \(len\) 的影响，发现只会影响 \(u,v\) 这两个点。貌似可以直接做？

好像有更简单的做法（真的简单吗）。

「雅礼集训 2017 Day5」珠宝

直接做是 \(nk\) 的背包~~很能冲直接开冲~~。

至少得优化一点吧。发现 \(c_i\) 的总数比较小，那就将相同的 \(c_i\) 分类，显然对同一体积取较大值，设 \(dp_{i,j}\) 为考虑到第 \(i\) 个价格，\(j\) 块钱能得到的最大价值，可以直接写转移：

\[dp_{i,j} = \max_{kc_i \leq j} dp_{i-1,j-kc_i}+w(i,k) \]

\(w(i,k)\) 指体积为 \(c_i\) 的物品买前 \(k\) 件价值。

发现这个 dp 把模 \(c_i\) 相同的拿出来，那就是若干个 \(dp_{i,j} = \max dp_{i-1,j-k}+w(k)\) 的形式，这个 \(w(k)\) 是一个凸函数，不难用四边形不等式分析出这个局部决策单调性。

「2020-2021 集训队作业」Gem Island 2

好想去摆烂啊。

先考虑拆期望，变成每种值在前 \(K\) 大中出现的方案数，设其为 \(F_i\)。

还是不好做，变成第 \(i\) 大值大于等于 \(j\) 的方案数。也就是算有 \(i\) 个数大于等于 \(j\) 的方案数。

容斥，设 \(f_{i,j}\) 为钦定 \(i\) 个数大于等于 \(j\) 的方案数, \(g_{i,j}\) 为恰好 \(i\) 个数大于等于 \(j\) 的方案数，那么有：

\[f_{i,j}=\binom{n}{i}\binom{n+m-(j-1)i-1}{n-1} \\ f_{i,j}=\sum_{k \ge i} \binom{k}{i}g_{k,j} \\ \Rightarrow g_{i,j} = \sum_{k\ge i}(-1)^{k-i}\binom{k}{i}f_{k,j} \\ Ans=\sum_{i,j} \min(i,K)g_{i,j} \]

来优化吧！

为了方便，上文的 \(i,j\) 互换并省去 \(j\)，我们继续推导。

\[g_{i} = \sum_{k\ge i}(-1)^{k-i}\binom{k}{i}\binom{n}{k}\binom{n+m-(j-1)k-1}{n-1} \]

后面这一大坨玩意不好搞，先看看答案长啥样：

\[Ans=\sum_j\sum_{i\leq n}\min(i,K)\sum_{k\ge i}(-1)^{k-i}\binom{k}{i}\binom{n}{k}\binom{n+m-(j-1)k-1}{n-1} \]

我们转换枚举顺序，变成：

\[\sum_j\sum_{k\leq n}\binom{n}{k}\binom{n+m-(j-1)k-1}{n-1}\sum_{i\leq k}(-1)^{k-i}\binom{k}{i}\min(i,K) \]

考虑后面这个东西，分成 \(i \leq K\) 和 \(i > K\) 讨论。

先来看 \(i \leq K\) 的情况，稍微推下可以得到：

\[\sum_{i \leq \min{k,K}}(-1)^{k-i}\binom{k}{i}i = k(-1)^{K+k}\binom{k-2}{K-1} \]

记为 \(t_k\)。

\[\sum_{i=K+1}^{k}(-1)^{k-i}\binom{k}{i}K=K(-1)^{K+k+1}\binom{k-1}{K} \]

记为 \(z_k\)。

这些都是容易计算的，答案现在是：

\[\sum_{k\leq n}(t_k+z_k)\binom{n}{k}\sum_{j \ge 1} \binom{n+m-(j-1)k-1}{n-1} \\ =\sum_{k\leq n}(t_k+z_k)\binom{n}{k}\sum_{j \ge 0} \binom{n+m-jk-1}{n-1} \]

到了这一步，我们最终还是要处理这个 \(\sum\limits_{j\ge 0}\binom{n+m-jk-1}{n-1}\) 的。

发现 \(jk\) 其实不超过 \(m\)。我们想到设一个 \(h_n = \sum\limits_{d|n}(t_d+z_d)\binom{n}{d}\)，我们用一个迪利克雷前缀和做到 \(m\log \log m\)，然后直接计算就可以了。