Description
给定一个 \(1 \sim n\) 的排列数组 \([P[1], P[2], \ldots, \ldots, P[n]]\) 。
现在给定一段代码，你可以对这个数组 \(P\) 进行任意次操作(可以不操作):
void modify(int P[], int n){
int l=rand()%n+1,r=rand()%n+1;
if (l>r) swap(l,r);
int minp=n;
for(int i=1;i<=r;++i)
minp=min(minp,P[i]);
for(int i=1;i<=r;++i)
P[i]=minp;
}
问最后能形成多少种不同的 \(P\) 数组，并对答案取模 \(10^{9}+7\) 。
例如， \(n=3, P=[1,3,2]\) 时
(1)不操作,得到 \([1,3,2]\) 。
(2)操作 \([1,2]\),得到 \([1,1,2]\) 。
(3)操作 \([1,3]\),得到 \([1,1,1]\) 。
(4)操作 \([2,3]\),得到 \([1,2,2]\) 。
可以证明至多只能形成这四种数组 \(P\) 。
\(n\le 5\times 10^3\)。
Solution
题目过于花里胡哨，简单来说，就是给出一个 \(1\sim n\) 的序列，每次操作可以使得区间 \([l,r]\) 里每一个数变成区间的最小值，问不同的序列个数。
首先对于一个 \(P_i\)，我们可以预处理出他所能影响到的左右端点，记为 \(L_i\) 和 \(R_i\)。
那么我们可以认为，\(P_i\) 可以使得区间 \([L_i,R_i]\) 中任意一个子区间的值变为 \(P_i\)，也可以是空区间，但只能是一个。
具体操作是可以先用 \(P_i\) 覆盖，然后再用比 \(P_i\) 小的 \(P_j\) 来覆盖不应该覆盖的地方。
考虑 \(dp\)，设 \(f_i\) 表示到了第 \(i\) 个区间 \([L_i,R_i]\) 的序列数。
转移 \(f_j=\sum_{k=L_i-1}^{j}f_k(L_i\le j\le R_i)\)。
时间复杂度 \(\mathcal O(n^3)\)，无法通过此题。
考虑优化，可以采取前缀和优化，转移式变为 \(f_j+=f_{j-1}(L_i\le j\le R_i)\)。
此时时间复杂度 \(\mathcal O(n^2)\)，空间复杂度 \(O(n)\)。
Code
#include<cstdio>
#define N 5005
#define mod 1000000007
using namespace std;
int n,a[N],l[N],r[N],f[N];
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i)
{
l[i]=r[i]=i;
while (a[i]<a[l[i]-1]) --l[i];
while (a[i]<a[r[i]+1]) ++r[i];
}
f[0]=1;
for (int i=1;i<=n;++i)
for (int j=l[i];j<=r[i];++j)
f[j]=(f[j]+f[j-1])%mod;
printf("%d\n",f[n]);
return 0;
}