A
题意：交互题。\(n\) 个人，每人有一个颜色。你每次可以询问一个集合中不同颜色数量。
最后输出每个人的颜色，只需保证相同的相同，不同的不同。\(n \le 150\)，交互次数不超过 \(3500\)。
考虑在区间 \([l, r]\) 找到与 \(x\) 颜色相同的编号最小的元素。
怎么判断 \(x\) 有没有在一个集合中出现过？先查询这个集合，在查询这个集合并上 \(x\)，比对两者是否相同。
思路很清晰了，如果在 \([l, mid]\) 出现，递归左区间；否则递归右区间。只需要区间长度对数次询问。
对于 \(i\) 找到对应的 \(ne_i\)，然后把相同颜色的一条链都找到。询问次数 \(O(n\log n)\) 可以通过。submission
B
题意：
C
题意：定义长度为 \(k\) 的序列 \(A\) 的权值等于不同的前缀最大值个数，记为 \(q(A)\)。
给定一个长度为 \(n\) 的排列 \(B\)，记他的一个子序列为 \(C\)，求所有 \(q(C)\) 的 \(m\) 次方之和。\(n \le 10^5, m \le 20\)。
\(m\) 很小，不难想到普通幂转下降幂：
\[\begin{aligned} \sum_{C \subseteq B} q(C)^m = \sum_{C \subseteq B} \sum_{k = 0}^m \begin{pmatrix}q(C)\\k\end{pmatrix} k! \begin{Bmatrix}m\\k\end{Bmatrix} \end{aligned} \]其中 \(\begin{pmatrix}q(C)\\k\end{pmatrix}\) 表示所有最大值中选了 \(k\) 个的方案数。不妨先选出一个严格上升子序列作为最大值，再在中间填数。
设 \(f(i, j)\) 表示 \(1 \sim i\) 选了 \(j\) 个最大值，且恰好选了第 \(i\) 个的合法子序列个数。
\[f(i, j) = \sum_{k < i\land B_k < B_i } f(k, j - 1)\times 2^{\sum_{l = k + 1}^{i} [B_l < B_i]} \]最后统计答案时有 \(\sum_{C}\begin{pmatrix}q(C)\\k\end{pmatrix} = \sum_{i} f(i, k) \times 2^{n - i}\)，复杂度瓶颈在于 f 的转移。
我们可以根据 j 一层一层 dp，加入 \(l\) 时将 \((B_l, n]\) 的答案乘 \(2\)，即 \(l\) 只会在 \(B_i > B_l\) 时会对已经存在的 \(f(k, j - 1)\) 产生 \(2\) 的系数。
把 \(f(l, j - 1)\) 加到 \(B_l\) 上。其中 \([1, B_i)\) 的和恰为 \(f(i, j)\)。
D
到底什么时候开始补网络流呢？
标签：begin,end,题意,16,sum,CSP2024,pmatrix,最大值 From： https://www.cnblogs.com/Luxinze/p/18402320