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 $ .