Weighted Increasing Subsequences

题意翻译

你有一个长度为 $n$ 的序列，定义 $a$ 的一个长度为 $k$ 的子序列为 $a_{i_1},a_{i_2},\dots,a_{i_k}$。由此，我们不难发现，$a$ 的一个长度为 $k$ 的子序列为上升子序列，当且仅当 $\forall j\in[1,k)$，$a_{i_j}<a_{i_{j+1}}$。 我们定义一个 $a$ 的一个长度为 $k$ 的上升子序列的权值为满足存在一个整数 $x\in(i_k,n]$ 使得 $a_x>a_{i_j}$ 的所有在 $[1,k]$ 内的整数 $j$ 的个数。现在，请你求出 $a$ 的所有上升子序列的权值和。由于答案可能很大，因此只需要输出答案对于 $10^9+7$ 取模之后的结果即可。 数据范围： - $1\leqslant t\leqslant 1000$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC 2022.1.4

题目描述

You are given the sequence of integers $ a_1, a_2, \ldots, a_n $ of length $ n $ . The sequence of indices $ i_1 < i_2 < \ldots < i_k $ of length $ k $ denotes the subsequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ of length $ k $ of sequence $ a $ . The subsequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ of length $ k $ of sequence $ a $ is called increasing subsequence if $ a_{i_j} < a_{i_{j+1}} $ for each $ 1 \leq j < k $ . The weight of the increasing subsequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ of length $ k $ of sequence $ a $ is the number of $ 1 \leq j \leq k $ , such that exists index $ i_k < x \leq n $ and $ a_x > a_{i_j} $ . For example, if $ a = [6, 4, 8, 6, 5] $ , then the sequence of indices $ i = [2, 4] $ denotes increasing subsequence $ [4, 6] $ of sequence $ a $ . The weight of this increasing subsequence is $ 1 $ , because for $ j = 1 $ exists $ x = 5 $ and $ a_5 = 5 > a_{i_1} = 4 $ , but for $ j = 2 $ such $ x $ doesn't exist. Find the sum of weights of all increasing subsequences of $ a $ modulo $ 10^9+7 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains the single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the sequence $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the sequence $ a $ . It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print the sum of weights of all increasing subsequences $ a $ modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5

输出样例 #1

4
12
0
6

说明

In the first test case the following increasing subsequences of $ a $ have not zero weight: - The weight of $ [a_1] = [6] $ is $ 1 $ . - The weight of $ [a_2] = [4] $ is $ 1 $ . - The weight of $ [a_2, a_3] = [4, 8] $ is $ 1 $ . - The weight of $ [a_2, a_4] = [4, 6] $ is $ 1 $ . The sum of weights of increasing subsequences is $ 4 $ .In the second test case there are $ 7 $ increasing subsequences of $ a $ with not zero weight: $ 3 $ with weight $ 1 $ , $ 3 $ with weight $ 2 $ and $ 1 $ with weight $ 3 $ . The sum of weights is $ 12 $ .

题意翻译

你有一个长度为 $n$ 的序列，定义 $a$ 的一个长度为 $k$ 的子序列为 $a_{i_1},a_{i_2},\dots,a_{i_k}$。由此，我们不难发现，$a$ 的一个长度为 $k$ 的子序列为上升子序列，当且仅当 $\forall j\in[1,k)$，$a_{i_j}<a_{i_{j+1}}$。 我们定义一个 $a$ 的一个长度为 $k$ 的上升子序列的权值为满足存在一个整数 $x\in(i_k,n]$ 使得 $a_x>a_{i_j}$ 的所有在 $[1,k]$ 内的整数 $j$ 的个数。现在，请你求出 $a$ 的所有上升子序列的权值和。由于答案可能很大，因此只需要输出答案对于 $10^9+7$ 取模之后的结果即可。 数据范围： - $1\leqslant t\leqslant 1000$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC 2022.1.4