题目大意
题目分析
神奇Dp。
直接考虑如何统计答案。
因为根据题目的最小表示法，在$i$数字出现时，$1\rightarrow i-1$必定出现过，因此我们可以枚举每一位$x$，再枚举这一位出现的数$v$，统计在$x$及其以前位已经确定与原序列相同时，有多少比原序列字典序更小的方案。
倘若将这些方案全部加起来即为答案。
设还有最后$i$位与原序列不同，前面的最大值为$j$，有$f[i,j]$种方案。
不难发现：
该状态转移分别表示在后一位填$1\rightarrow j$与填$j$的方案数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=10005;
const LL mod=1e6+7;
int n,f[maxn][maxn],a[maxn];
LL ans=0;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int(),f[0][i]=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
f[i][j]=((LL)j*f[i-1][j]+f[i-1][j+1])%mod;
int Max=1;
for(int i=2; i<=n; i++) {
for(int j=1; j<a[i]; j++)ans=(ans+f[n-i][max(Max,j)])%mod;
Max=max(Max,a[i]);
}
printf("%lld\n",(ans+1)%mod);
return 0;
}
|
