CF660E
考虑从子序列从第一次出现的地方去贡献每个数列。
如果我们有一个子序列为 \(a_{p_1},a_{p_2},a_{p_3},\cdots,a_{p_i}\)，那我们要求：\(a_{p_i}\) 在 \(a_{p_{i-1}+1\sim p_i}\) 中第一次出现。
容易列出式子：\(\sum_{i=1}^n m^i \sum_{j=i}^n \binom{j-1}{i-1}(m-1)^{j-i}m^{n-j}\)。其中 \(i\) 枚举的是子序列的长度，\(j\) 枚举的是 \(p_i\)。
化简：$$\begin{aligned} &\sum_{i=1}^n m^i \sum_{j=i}^n \binom{j-1}{i-1}(m-1){j-i}m\ =& \sum_{j=1}n\sum_{i=1}j \binom{j-1}{i-1}(m-1){j-i}m\ =&\sum_{j=1}n\sum_{i=1}j \binom{j-1}{i-1}(m-1){(j-1)-(i-1)}m\ =&\sum_{j=1}^n m{n-(j-1)}\sum_{i=0} \binom{j-1}{i}(m-1){(j-1)-i}m\ =&\sum_{j=1}^n m{n-(j-1)}(2m-1)\ =&\sum_{j=0}^{n-1} m{n-j}(2m-1)\ \end{aligned}$$
注意空子序列要单独计算，贡献为 \(m^n\)。
CF1930E
令最终 \(a_i\) 被删去记作 \(0\)，否则记作 \(1\)。
01 序列合法的充要条件为：
- \(0\) 的数列为 \(2k\) 的倍数。
- 存在 \(1\) 满足左右都至少存在 \(k\) 个 \(0\)。
证明：考虑回撤最后一次操作。首先在这个 \(1\) 左右两边各选 \(k-1\) 个 \(0\) 变成 \(1\)。如果左边的 \(0\) 多，那任意标记一个右边的 \(0\)，然后标记处于中间位置的 \(0\) 为 \(1\)（显然在左边）。否则反之。发现子问题满足上述约束，递归证明命题。
枚举 \(k\) 和操作次数 \(c\)，用所有方案 \(\binom{n}{2ck}\) 减去不合法的方案。
不合法的方案满足：左边第 \(k\) 个 \(0\) 到右边第 \(k\) 个 \(0\) 之间都是 \(0\)。把这 \(x=2ck-2k+2\) 个 \(0\) 缩起来，相当于在 \(n-x+1\) 个位置中选出 \(2k-1\) 个 \(0\)。
CF1784D
从根往下考虑，设 \(f_{i,u}\) 表示 \(u\) 是子树内第 \(i\) 层的胜者，且考虑了除了 \(u\) 的对手子树外的排列方案数。
\(f_{0,u}=[u=0],f_{i,u}=2\times(2^{n-i})!\binom{2^n-2^{n-i}-u}{2^{n-i}-1}\sum_{j=1}^{u-1}f_{i-1,j}\)
其中 \(f_{0,u}=[u=0]\) 表示一开始是一个虚拟的胜者，并不知道其具体是什么。系数的意义：\(2\) 表示蓝色、黑色两棵子树不关心顺序；\((2^{n-i})!\) 表示确定黑色子树内的数的顺序；\(\binom{2^n-2^{n-i}-u}{2^{n-i}-1}\) 表示黑色子树内最小值已经被我们后面那个枚举确定，然后其他的 \(2^{n-i}-1\) 个数需要我们从 \((j,2^n]\) 中确定。
最终 \(u\) 的答案为 \(\sum_{j=1}^{u-1}f_{n,j}\)，时间复杂度 \(O(2^nn)\)。
CF1976E
补
CF1558D
考虑我们最终的序列为 \(a_{p_1},a_{p_2},\cdots,a_{p_n}\)。我们有一些限制：\(a_{p_i}\le a_{p_{i+1}}\) 或 \(a_{p_i}<a_{p_{i+1}}\)。
如果我们有 \(x\) 个小于号，\(n-1-x\) 个小于等于号，方案数为：\(\binom{2n-1-x}{n}\)。
考虑模拟计算 \(x\)，可以使用平衡树或者线段树。复杂度 \(O(m\log n)\)。
具体维护方法：倒序枚举这些插入 \((x_i,y_i)\)，那么对于当前的第 \(y_i\) 个数 \(p\) 和 \(y_i+1\) 个数 \(q\)，表示 \(p\) 插入到 \(q\) 前面了，于是我们把 \(p\) 删除，给 \(q\) 打上 \(tag\)，表示 \(q\) 前面的小于号。最后数 \(tag\) 个数即可。
CF1781F
使用经典转化，
(看作 1，)看作 -1，合法：前缀和全部都是非负。
第 \(i\) 次插入到某个位置的概率为 \(\frac{1}{2i-1}\)，可以最后乘。
发现插入()等于把前缀和数组中 \(x\rightarrow x,x+1,x\)，)(等于把前缀和数组中 \(x\rightarrow x,x-1,x\)。
设 \(f_{i,x}\) 表示一开始前缀和为 \(x\)，没有任何括号，然后插入 \(i\) 次后合法的方案数。
\(f_{n,x}=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}p\binom{n-1}{i}\binom{n-i-1}{j}f_{i,x}f_{j,x+1}f_{n-i-j-1,x}+\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(1-p)\binom{n-1}{i}\binom{n-i-1}{j}f_{i,x}f_{j,x-1}f_{n-i-j-1,x}\)
转移式是三个东西卷积，复杂度 \(O(n^4)\)。考虑先预处理其中两个卷积，然后再与第三个卷就好了。复杂度 \(O(n^3)\)。
CF1716F
有人机式子：\(\sum_{i=0}^{n}i^k\binom{n}{i}x^iy^{n-i}\)，其中 \(x=\left\lceil\frac{m}{2}\right\rceil,y=\left\lfloor\frac{m}{2}\right\rfloor\)。
考虑使用第二类斯特林数。$$\begin{aligned} &\sum_{i=0}n\sum_{j=0}kS_2(k,j)i^{\underline j}\binom{n}{i}xiy\ =&\sum_{i=0}n\sum_{j=0}kS_2(k,j)n^{\underline j}\binom{n-j}{i-j}xiy\ =&\sum_{j=0}kS_2(k,j)nxj\sum_{t=0}\binom{n-j}{t}x{t}y\ =&\sum_{j=0}kS_2(k,j)nxjm\ \end{aligned}$$
CF1924D
不妨令 \(n>m\)。先考虑经典问题：有 \(k\) 对括号，合法的括号序列方案数为 \(\binom{2k}{k}-\binom{2k}{k-1}\)。
仍然考虑走路。从 \((0,0)\) 走到 \((n+m,n-m)\)。考虑如何求最大合法括号子序列？记录一个 \(tot\) 表示左括号数列，如果遇到右括号就tot--,ans++，前提是tot>0。
考虑模拟这个走路的过程。在原本的图像上，每次突破最小值就会导致这个括号不被计算，于是我们要求最低点为 \(k-m\) 的折线个数。
对于 \(k>m\) 无解。考虑差分，设 \(f_t\) 表示最低点小于等于 \(t\) 的方案数。那我们求 \(f_{k-m}-f_{k-m-1}\)。
对于 \(f_t\)，我们考虑将触及 \(t\) 的线段从第一个交点处翻转，那我们求 \((0,0)\rightarrow (n+m,2t-(n-m))\)，即 \(f_t=\binom{n+m}{n-t}\)。
CF2030G2
对于 \(S\)，这个公共点在哪里？答案是将这 \(2|S|\) 个端点进行排序，中位数即为公共点。将线段分成 3 类可以证明。
那我们从中位数去统计答案补
CF1750G