Yet Another Array Counting Problem
题意翻译
### 题目描述
对于长度为 $n$ 的序列 $x$，定义其在子段 $[l;r]$ 的“最左端最大值位置”为最小的满足 $l\leq i\leq r$ 且 $x_i=\max_{j=l}^rx_j$ 的整数 $i$。
给定整数 $n,m$ 和长度为 $n$ 的序列 $a$，你需要求出满足下列要求的序列 $b$ 的数量：
- 序列 $b$ 长度为 $n$，且对任意整数 $i(1\leq i\leq n)$ 都有 $1\leq b_i\leq m$ 成立。
- 对任意整数 $l,r(1\leq l\leq r\leq n)$，总有 $a,b$ 在子段 $[l;r]$ 的“最左端最大值位置”相同。
答案对 $10^9+7$ 取模。
每个测试点包含多组数据。
### 输入格式
第一行输入一个整数 $t(1\leq t\leq10^3)$ 表示数据组数，接下来对于每组数据：
第一行输入两个整数 $n,m(2\leq n,m\leq2\times10^5;\sum n\times m\leq10^6)$。
接下来输入一行 $n$ 个整数表示序列 $a(1\leq a_i\leq m)$。
### 输出格式
对于每组数据：
输出满足要求的序列 $b$ 的数量对 $10^9+7$ 取模后的值。
### 样例解释
- 对于第一组数据：
- 下面是所有 $8$ 个满足要求的序列 $b$：
$[1,2,1],[1,2,2],[1,3,1],[1,3,2],[1,3,3],[2,3,1],[2,3,2],[2,3,3]$。
- 对于第二组数据：
- 下面是所有 $5$ 个满足要求的序列 $b$：
$[1,1,1,1],[2,1,1,1],[2,2,1,1],[2,2,2,1],[2,2,2,2]$。
题目描述
The position of the leftmost maximum on the segment $ [l; r] $ of array $ x = [x_1, x_2, \ldots, x_n] $ is the smallest integer $ i $ such that $ l \le i \le r $ and $ x_i = \max(x_l, x_{l+1}, \ldots, x_r) $ .
You are given an array $ a = [a_1, a_2, \ldots, a_n] $ of length $ n $ . Find the number of integer arrays $ b = [b_1, b_2, \ldots, b_n] $ of length $ n $ that satisfy the following conditions:
- $ 1 \le b_i \le m $ for all $ 1 \le i \le n $ ;
- for all pairs of integers $ 1 \le l \le r \le n $ , the position of the leftmost maximum on the segment $ [l; r] $ of the array $ b $ is equal to the position of the leftmost maximum on the segment $ [l; r] $ of the array $ a $ .
Since the answer might be very large, print its remainder modulo $ 10^9+7 $ .
输入输出格式
输入格式
Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of test cases.
The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \le n,m \le 2 \cdot 10^5 $ , $ n \cdot m \le 10^6 $ ).
The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le m $ ) — the array $ a $ .
It is guaranteed that the sum of $ n \cdot m $ over all test cases doesn't exceed $ 10^6 $ .
输出格式
For each test case print one integer — the number of arrays $ b $ that satisfy the conditions from the statement, modulo $ 10^9+7 $ .
输入输出样例
输入样例 #1
4
3 3
1 3 2
4 2
2 2 2 2
6 9
6 9 6 9 6 9
9 100
10 40 20 20 100 60 80 60 60输出样例 #1
8
5
11880
351025663说明
In the first test case, the following $ 8 $ arrays satisfy the conditions from the statement:
- $ [1,2,1] $ ;
- $ [1,2,2] $ ;
- $ [1,3,1] $ ;
- $ [1,3,2] $ ;
- $ [1,3,3] $ ;
- $ [2,3,1] $ ;
- $ [2,3,2] $ ;
- $ [2,3,3] $ .
In the second test case, the following $ 5 $ arrays satisfy the conditions from the statement:
- $ [1,1,1,1] $ ;
- $ [2,1,1,1] $ ;
- $ [2,2,1,1] $ ;
- $ [2,2,2,1] $ ;
- $ [2,2,2,2] $ .