注意，本篇文章均为嘴巴，无任何可信度。
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\)，然后直接计算就可以了。
总结
好像这几天就没写什么，已经菜死了。
标签：min,嘴巴,ge,leq,形状,sum,binom,变成,dp From： https://www.cnblogs.com/hikkio/p/17889035.html