一些 trick (10) | 不少于一半？随机化！
MatrixGroup
·
·
算法·理论
例题 1. CF1523D
给定 n 个集合，每个集合都是 1\sim m 的整数组成的，大小不超过 p，请选出不少于一半的集合，最大化它们交集的大小。构造出一个这样的交集。
“不少于一半”引导我们去随机化。考虑钦定一个选定的集合，重复多次便有大概率选到答案。钦定选定集合后，直接高维度前缀和处理即可。
例题 2. [CF364D](https://codeforces.com/problemset/problem/364/D)
给定一个多重集 $a_1,a_2,\cdots,a_n$，请选出一个大小不小于原集一半的子集，最大化其 $\gcd$。
$n\le10^6,1\le a_i\le10^{12}$。
“不少于一半”引导我们去随机化。考虑钦定一个数 $a_i$，重复多次便有大概率选到答案。选出它所有的因数（不超过 $d=6720$ 个），对于每个 $a_j$ 求出 $\gcd(a_i,a_j)$，然后平方 dp 求出每个因数被覆盖了多少次，统计答案即可。
已经加入 [一些 trick](https://www.luogu.com.cn/blog/483824/some-tricks)。