zroi2525 分组
钦定选中的人都被选到 \(\text{A}\) 组的概率，分别考虑枚举 \(\text{A}\) 组被放完和 \(\text{B}\) 组被放完的的方案数：
记 \(lst\) 为最后一个被选中的人的位置，\(s_i\) 为 \(1-i\) 中被选中的人的个数。
\(\text{A}\) 组被放完：
\[F(A)=2^{2n}\cdot\sum_{i=\max(n,lst)}^{2n-1}{i-1-s_{i-1} \choose n-1-s_{i-1}}2^{-i} \]\(\text{B}\) 组被放完：
\[F(B)=2^{2n} \cdot \sum_{i=n}^{2n-1}{i-1-s_{i-1} \choose n-1}2^{-i} \]推到这里的话，就已经得到了一个 \(O(nq)\) 的做法，可以通过 \(70pts\) 。
考虑继续优化下去，将 \(s_i\) 相同的一起计算，那么只会分成 \(\sum k\) 段，每一段内可以 \(O(1)\) 求解。
具体计算方法，现在我们要计算一个形如如下式子的值：
\[\sum_{i=l}^r{i-1-v \choose w}2^{-i} \]对于所有的询问 \(w\) 都是一个定值等于 \(n-1\) ，因此 \(F(B)\) 的计算分段之后每一段可以通过预处理组合数的前缀和 \(O(1)\) 的计算出来。
对于 \(F(A)\) 的计算，本质不同的 \(s_{i-1}\) 只有 \(\sqrt{\sum_k}\) 个，也是直接计算就好。
然后这题就做完了，复杂度 \(O(n\sqrt{\sum k})\) 。
这种类型的概率 \(\text{dp}\) 要与组合计数结合起来，不要只会写最基础的 \(\text{dp}\) 。题目的一些限制要求可以通过钦定一些东西来维护。
vp:Codeforces Round 850
这场 \(\text{E}\) 、\(\text{F}\) 之前做过，来写只是为了锻炼前几题。
CF1786D. Letter Exchange
这题贪心的思路很显然，但是直接像我赛时实现的做法代码量有些复杂。
这类题目可以考虑转化成图论求解，缺字母，多字母转化成图上的边，代码量会简单许多。
vp: Codeforces Round 852
CF1793B. Fedya and Array
这类题目考虑特殊情况来构造。既然峰、谷的和各位 \(x,y\) ，我们不妨构造让整个序列只有一个峰和谷。
具体方法如下：
\[y,y+1,...,x,x-1,x-2,...,y+1 \]对于一类没有思路的构造题，不妨考虑特殊情况。
CF1793E. Velepin and Marketing
挺好想的一道题。首先可以发现被满足的人一定是排完序后从小到大的一段前缀。因此我们考虑记 \(f_i\) 表示前 \(i\) 个人被满足，至多能被分成的组数。
这个部分可以很显然的 \(\text{dp}\) 预处理，特别注意一下可以让后面的人来填补。
CF1793F. Rebrending
离线将询问按照右端点排序，考虑右端点右移的过程。
现在要将 \(a_i\) 维护进来，我们先只考虑其与其后继的贡献，与前驱的将序列翻转过来再做一遍即可。
记 \(a_i\) 之前最靠后的大于 \(a_i\) 的数为 \(a_j\) 。如果前面还有一个 \(a_k\) 也能做贡献，首先必须满足 \(a_i<a_k<a_j\) ，由于 \(a_j,a_k\) 之间可以做贡献，所以还需要满足 \(a_k-a_i<a_j-a_k\) ，移项整理得：
\[a_k<\frac{a_i+a_j}{2} \]故最多往前跳 $\log $ 次，直接权值线段树维护即可，时间复杂度 \(O(n \log^2 n)\) 。
标签：13,text,sum,2023.2,choose,考虑,2n,dp From： https://www.cnblogs.com/oscaryangzj/p/17117897.html