两个序列任意选相同数量元素

· · 算法·理论

标题应该叫什么。？

给定序列 a=(a_1,a_2,...,a_n)，b=(b_1,b_2,...,b_m)。

对于问题：从 a，b 中分别选出 k 个元素。

解决方案：考虑 a 选了的和 b 没选的元素加起来恰好 m 个。

这样，k 的具体值我们就不用关心了。

例 1：

\displaystyle \sum\limits_{k=0}^n\binom{n}{i}\binom{m}{i}

多组询问，1\le q\le10^6，1\le n\le m\le10^6。

考虑上述思路，相当于从 n+m 个物品中任意选 m 个物品的方案数。

其中前 n 个物品中当前选到表示原来的选到，后 m 个物品中选到表示原来的没选到。

原式 \displaystyle=\binom{n+m}{m}=(n+m)!(n!)^{-1}(m!)^{-1}，预处理阶乘逆元即可。

例 2：

需要维护多重集合 a 和 b：

$2$，在 $a$ 和 $b$ 中选择相同数量的元素，最小化选出元素之和并输出。 操作 $10^6$ 次。 --- 先考虑正常做法。 维护一个权值线段树或树状数组，由于（排序后）选出的 $a$ 和 $b$ 单调递减，二分选择的元素数量 $k$ 使得 $a_k+b_k<0$ 即可。 因为在权值处维护，$a_k$ 和 $b_k$ 不在数据结构的同一位置。发现二分放不进去数据结构里，只能做到 $O(n\log^2{n})$。 --- 考虑用上面的技巧。 $a$ 选的和 $b$ 不选的元素总数一定是 $b$ 的元素总数。 稍微转换一下，先钦定选了所有的 $b_i$，然后把 $a_i$ 和 $-b_i$ 放进线段树或树状数组。 想要找到桶中的前 $m$ 个之和，显然线段树或树状数组二分，时间复杂度 $O(n\log{n})$。 --- 总结：以上面的为例，排列组合等价的东西实在是太多了，因此彻底明白本质是困难的，我们只需要找到一条路径就可以。