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

题意翻译

### 题目描述 对于长度为 $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]$。