题目A

给定一个长度为 $n$ 的数组 $a$，必须删除一个下标区间 $[L \sim R]$ 的数，让剩下的数满足非严格升序。问有多少种合法方案。全部删掉也是一种合法方案。$1 \le n \le 10^5$

思路：数组下标 $[0 \sim n - 1]$，从后往前扫描，使得 $[X \sim n - 1]$ 这一段是非严格升序。之后枚举删除区间的左端点，比如一开始 $L = 0$，那么右端点大于等于 $X - 1$，继续枚举 $L = 1$，右端点在 $[X \sim n - 1]$ 中二分找第一个大于等于 $a_0$ 的数，假设这个位置是 $p$，那么右端点大于等于 $p - 1$。以此类推，直到左边剩下的数出现了降序。

题目B

给定一个长度为 $n$ 的数组 $a$，任选一些数字相乘得到乘积 $x$，$x$ 的价值为 $x$ 的不同质因子数量。问在所有选择方案中，得到的所有 $x$ 的价值之和，结果对 $10^9+7$ 取模。数组的任意一个子集都是一种选择方案。$1 \le n \le 2 \times 10^5$，$1\le a_i \le 10^6$

思路：对每个数分解质因子，记录每个质数的出现次数，对于质数 $p$，如果其在 $a_j$ 中出现，那么 ++ cnt[p] ，只加一次。不关心 $p$ 的指数。统计完之后，根据每个质数对最终答案的贡献计算结果。比如质数 $p$，假设 f = cnt[p], g = n - cnt[p]; ，即有 $f$ 个数中含有质因子 $p$，$g$ 个数中不含。$p$ 要产生贡献则要在 $f$ 个数中至少选择一个，方案数是 $C_f^1+C_f^2+\cdots+C_f^f=2^f-1$，剩下的 $g$ 个数每个都是可选可不选，$2^g$ 种方案，乘法原理，$p$ 的总贡献就是 $2^g\times(2^f-1)$。快速幂。对每个质数都算一遍就行了。