\(\text{Contest 1}\)
\(\text{Heavenly Altitudes}\)
\(\text{description}\)
给你一个集合 \(S = \{1, 2, ..., n\}\)，要求分成 \(m\) 段，段之间不考虑顺序，段中的元素不考虑顺序，现给你每段的最小值 \(a_1, a_2, ..., a_m\)，求有多少种合法的划分方式，答案对 \(10^9 + 7\) 取模。
\(1 \le n \le 10^6\)。
\(\text{solution}\)
十多分钟手刃了。
考虑到一定是从大到小考虑，因为大的不会对小的造成更多影响。
假设已经从大到小排序，根据组合直觉，答案应该是：
\[\sum_{i = 1}^m \binom{n - a_i - (m - i)\frac{n}{m}}{\frac{n}{m} - 1} \]因为组合意义算就好了（每次剩下的数是固定的）。
\(\text{Seeker Temple}\)
\(\text{description}\)
给定 \(n\) 个质数 \(a_1, a_2, ..., a_n\)，定义一个集合 \(S = \{x|x = a_1^{p_1}a_2^{p_2}...a_n^{p_n}\}\)，其中 \(p_1, p_2, ..., p_n \ge 0\)，问你 \(S\) 中第 \(k\) 小的数是多少。
\(1 \le n \le 16, 2 \le a_1, a_2, ..., a_n \le 100, 1 \le ans \le 10^{18}\)。
\(\text{solution}\)
这个题确实挺好的。
根据数学直觉和部分分，那么这个集合里的数一定不会太多，但是仍然有 \(10^8\) 左右的级别，考虑到有 \(n \le 8\) 的部分分，我们考虑拆成两个部分分别处理出来 \(S\) 集合，如果我们是随机的话，那么两个集合都是不会大于 \(10^6\) 这个级别（其实只有 \(10^5\) 级别左右），考虑我们二分答案，每次检查答案是否合法就把两个 \(S\) 集合合并起来，算一下（里面再套个二分），这样子复杂度就是 \(O(n \log^2 n)\) 级别的了。
主要是要想到折半（其实也没有什么套路）。
标签：...,le,10,text,2024,CT02,集合,考虑,模拟 From： https://www.cnblogs.com/alexande/p/18336832