第三题

给定一个长度为 $n$ 的数组 $a$，最多可以进行一次操作，选择一个区间，要求区间内的元素都是偶数，你可以把这个区间内每个元素都除以 $2$。希望最终所有元素之和尽可能大，输出这个最大的和。$1 \le n \le 10^5$，$-10^9 \le a_i \le 10^9$

思路：预处理数组 $b$，$b_i=a_i/2 - a_i$，就是把这个数除以 $2$ 的收益。找出所有的偶数段，对于每一个偶数段 $[L\sim R]$，DP求最大子数组，LeetCode 53。把最大的一个DP结果（当然要大于0）加到原数组的和上就是答案。

第四题

给定一个长度为 $n$ 的数组 $a$，请求出把每个数的阶乘都乘起来得到的大数的因子的个数。结果对 $10^9+7$ 取模。$1 \le n \le 2\times10^5$，$1 \le a_i \le 10^6$

思路：需要得到最终的乘积的质因子分解的结果。对 $a$ 升序排序。最大值假设是 $m$，先把 $m$ 以内的质数筛出来，需要用线性筛。然后枚举 $[2\sim m]$，枚举的是阶乘的因子，假设当前枚举到了 $j$，由于已经排序了，所以很容易求出来 $j$ 出现了多少次，只有大于等于 $j$ 的数的阶乘中才会出现 $j$，（这一步也不需要二分，用一个指针维护即可），对 $j$ 分解质因数，每个质因子的指数乘上 $j$ 的出现次数，这就是 $j$ 对最终结果的贡献。时间复杂度 $O(m\log m)$