CF1621G Weighted Increasing Subsequences

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。 长度为 $k$ 的下标序列 $i_1 < i_2 < \ldots < i_k$ 表示原序列 $a$ 的一个子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$。 如果对于每个 $1 \leq j < k$ 都有 $a_{i_j} < a_{i_{j+1}}$，则称该子序列为递增子序列。 对于序列 $a$ 的长度为 $k$ 的递增子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$，其权值定义为满足以下条件的 $1 \leq j \leq k$ 的个数：存在下标 $i_k < x \leq n$，且 $a_x > a_{i_j}$。 例如，若 $a = [6, 4, 8, 6, 5]$，下标序列 $i = [2, 4]$ 表示递增子序列 $[4, 6]$。该递增子序列的权值为 $1$，因为对于 $j = 1$，存在 $x = 5$ 使得 $a_5 = 5 > a_{i_1} = 4$，但对于 $j = 2$，不存在这样的 $x$。 请你求出所有递增子序列的权值之和，结果对 $10^9+7$ 取模。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示序列 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示序列 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出所有递增子序列的权值之和，对 $10^9+7$ 取模。

在第一个测试用例中，以下递增子序列的权值不为零： - $[a_1] = [6]$ 的权值为 $1$。 - $[a_2] = [4]$ 的权值为 $1$。 - $[a_2, a_3] = [4, 8]$ 的权值为 $1$。 - $[a_2, a_4] = [4, 6]$ 的权值为 $1$。 递增子序列的权值之和为 $4$。 在第二个测试用例中，有 $7$ 个递增子序列权值不为零：$3$ 个权值为 $1$，$3$ 个权值为 $2$，$1$ 个权值为 $3$。权值之和为 $12$。 由 ChatGPT 4.1 翻译