题解

思路

1. 拆分单个位置的贡献

固定位置 $i$，令 $p_i$ 为 $i$ 右侧最后一个满足 $a_{p_i}>a_i$ 的位置；若不存在则记为无效。

一个包含位置 $i$ 的递增子序列会让 $i$ 贡献 $1$，当且仅当该子序列的末尾位置严格小于 $p_i$。因此位置 $i$ 的总贡献可以拆成：

1. 以 $i$ 结尾的递增子序列数 $L_i$；
2. 从 $i$ 开始、且最后位置小于 $p_i$ 的递增延伸数 $G_i$（允许不再选择元素）。

二者可以任意拼接，故答案为

$$\sum_i L_iG_i\pmod {10^9+7}.$$

做法

子任务 1：枚举子序列

当 $n\le18$ 时枚举所有非空下标集合，检查是否严格递增。设末尾为 $r$，再求 $r$ 后方最大值，逐个判断所选元素是否产生贡献。复杂度为 $O(2^n n)$。

子任务 2：二次动态规划

先计算不限制末尾的后缀方案数

$$F_i=1+\sum_{j>i,\ a_j>a_i}F_j.$$

若 $p_i$ 存在，则 $p_i$ 后方所有数都不大于 $a_i$。对 $i<j<p_i$：

• 若 $a_j\ge a_{p_i}$，从 $j$ 出发的任何严格递增延伸都不可能选择 $p_i$ 或其后位置，可以直接加入 $F_j$；
• 若 $a_i<a_j<a_{p_i}$，则 $p_j=p_i$，应加入已经计算的 $G_j$。

再计入“不继续选择”的一种方案，有

$$G_i=1+ \sum_{\substack{i<j<p_i\\a_j\ge a_{p_i}}}F_j+ \sum_{\substack{i<j<p_i\\a_i<a_j<a_{p_i}}}G_j.$$

倒序直接枚举转移即可做到 $O(n^2)$。

子任务 3：非递增序列

严格递增子序列只能取一个元素，而其右侧不存在更大的值，所以所有权值均为 $0$。

满分算法

将数值离散化。$L_i$ 是标准的递增子序列计数，可从左到右用树状数组维护值域前缀和：

$$L_i=1+\sum_{j<i,\ a_j<a_i}L_j.$$

倒序计算 $F_i,G_i$ 时维护两棵树状数组：

• 第一棵按值维护所有已处理位置的 $F$，并在比所有离散值都大的哨兵处放入 $1$，代表空延伸；
• 第二棵按值维护已经求出的 $G$。

于是

$$F_i=\sum_{v>a_i}\mathrm{BIT}_F(v),$$

并且当 $p_i$ 存在时

$$G_i= \sum_{v\ge a_{p_i}}\mathrm{BIT}_F(v)-F_{p_i} +\sum_{a_i<v<a_{p_i}}\mathrm{BIT}_G(v).$$

第一项中的哨兵自动给出空延伸；减去 $F_{p_i}$ 正好排除选取 $p_i$ 的方案。$p_i$ 可用后缀最大值二分，或倒序以值域最大位置数据结构求得。

复杂度

枚举算法为 $O(2^n n)$，二次动态规划为 $O(n^2)$，非递增支线为 $O(n)$。满分算法对每个测试用例的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$；多测时将 $n$ 换成所有测试用例规模之和。