题目描述
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
样例输入 #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] $ .
不妨设现在递归到了区间 \([l,r]\)
此时，我们可以用 ST 表求出 \([l,r]\) 靠左的最大值所在的位置，设在 \(k\) 吧。那么所有跨越了 \(k\) 的区间的最左最大值都在 \(k\)。有一点区间dp的痕迹。
然后定义 \(dp_{l,r,x}\) 为区间 \([l,r]\) 中的最大值至多为 \(x\) 的方案数。\(dp_{l,r,x}=dp_{l,k-1,x-1}\times dp_{k+1,r,x}+dp_{l,r,x-1}\)。这是因为所有跨越了点 \(k\) 的区间的左最大值都要在 \(k\)，所以我们枚举 \(k\) 填什么，然后递归到左右两边计算。那么我们有了一个 \(O(n^2m)\) 的算法。
注意到真正有用的区间只有 \(O(n)\) 个，所以我们可以给区间编个号，然后进行上面的 dp。复杂度降到 \(O(nm)\)，就可以过了。注意由于题目保证的是 \(nm\le10^5\)，所以要进行一个二维压一维。
#include<bits/stdc++.h>
const int N=2e5+5,P=1e9+7;
struct node{
int mx,wh;
node operator+(const node&n)const{
if(n.mx>mx)
return n;
return (node){mx,wh};
}
}st[N][25];
int t,n,m,dp[3000005],lg[N],idx,x;
node ask(int l,int r)
{
int k=lg[r-l+1];
return st[l][k]+st[r-(1<<k)+1][k];
}
int turn(int x,int y)
{
return x*(m+3)+y;
}
int dfs(int l,int r)
{
if(l>r)
return 0;
int o=++idx;
node k=ask(l,r);
int lc=dfs(l,k.wh-1);
int rc=dfs(k.wh+1,r);
// printf("%d %d %d %d %d\n",o,l,r,lc,rc);
for(int j=1;j<=m;j++)
(dp[turn(o,j)]=dp[turn(o,j-1)]+1LL*dp[turn(lc,j-1)]*dp[turn(rc,j)]%P)%=P;
// for(int j=1;j<=m;j++)
// printf("%d ",dp[turn(o,j)]);
// puts("");
return o;
}
int main()
{
scanf("%d",&t);
for(int i=2;i<N;i++)
lg[i]=lg[i>>1]+1;
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&x),st[i][0]=(node){x,i};
for(int i=1;i<=lg[n];i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[j][i]=st[j][i-1]+st[j+(1<<i-1)][i-1];
idx=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<=m;i++)
dp[turn(0,i)]=1;
dfs(1,n);
printf("%d\n",dp[turn(1,m)]);
}
}