题解一（无作者名）

#include<iostream>
using namespace std;
typedef long long ll;
ll n,i,j,k,x,ans,p=1000007,mx[10005],a[10005],dp[10005];
int main(){
	cin>>n;
	for(i=1;i<=n;i++) dp[i]=1,cin>>a[i],mx[i]=max(mx[i-1],a[i]);//前缀最大值 
	for(i=n;i;i--){
		//第i个人的队伍编号最多是mx[i-1]+1 
		for(j=1;j<=min(mx[i-1]+1,a[i]-1);j++) ans=(ans+dp[max(j+1,mx[i-1]+1)])%p;
		for(j=1;j<=i;j++) dp[j]=((j-1)*dp[j]+dp[j+1])%p;//滚动数组优化 
	}
	cout<<(ans+1)%p;//当前ans是多少方案比a小，ans+1后就是排名了 
	return 0;
}

by tangjiahua

#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1000007;
ll n,a[10010],mx[10010],dp[10010];
//dp[i,j]表示前i个人编号最大为j的合法序列数（需要滚动数组） 
//我们需要求字典序<原序列的合法序列数 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mx[i]=max(mx[i-1],a[i]);//记录前缀最大值 
		dp[i]=1;//初始化 
	}
	ll ans=1;//因为统计的是字典序<原序列的合法序列数，所以还要算上原序列 
	for(int i=n;i>=2;i--){//枚举从第i位开始与原序列不同 
		ans=(ans+(a[i]-1)*dp[max(mx[i-1],a[i]-1)])%mod;
		//枚举第i位选1~a[i]-1的方案数，后面可以随便选 
		for(int j=1;j<=i;j++)dp[j]=(dp[j]*j+dp[j+1])%mod;//更新数组，当最大编号为j时第i位可以选择1~j共j个或建一个新的队伍j+1 
	}
	cout<<ans;
	return 0;
}

by taojinghua+fuxuanyuan

#include<iostream>
using namespace std;
typedef long long ll;
ll n,i,j,k,x,ans,p=1000007,mx[10005],a[10005],dp[10005];
int main(){
    cin>>n;
    for(i=1;i<=n;i++) dp[i]=1,cin>>a[i],mx[i]=max(mx[i-1],a[i]);//前缀最大值 
    for(i=n;i;i--){
        //第i个人的队伍编号最多是mx[i-1]+1 
        ans=(ans+dp[mx[i-1]+1]*(a[i]-1)%p)%p;
        /*
            原方法:for(j=1;j<=a[i]-1;j++)ans=(ans+dp[mx[i-1]+1])%p;
            既然mx[i-1]+1为第i个人的队伍编号最大,则若a[i]-1>=mx[i-1]+1(即a[i]>mx[i-1]),此状态不合法,故for(j=1;j<=a[i]-1;j++)
            同理,mx[i-1]+1也绝不小于j+1,故ans=(ans+dp[mx[i-1]+1])%p;
            所以a[i]-1为可行个数,dp[mx[i-1]+1]为贡献队伍的情况个数。 
            可转化为ans=(ans+dp[mx[i-1]+1]*(a[i]-1)%p)%p;
        */
        for(j=1;j<=i;j++) dp[j]=((j-1)*dp[j]+dp[j+1])%p;//滚动数组优化 
    }
    cout<<(ans+1)%p;//当前ans是多少方案比a小，ans+1后就是排名了 
    return 0;
}

#include<iostream>
using namespace std;
typedef long long ll;
ll n,i,j,k,x,ans,p=1000007,mx[10005],a[10005],dp[10005];
int main(){
	cin>>n;
	for(i=1;i<=n;i++) dp[i]=1,cin>>a[i],mx[i]=max(mx[i-1],a[i]);//前缀最大值 
	for(i=n;i;i--){
		//第i个人的队伍编号最多是mx[i-1]+1 
		for(j=1;j<=min(mx[i-1]+1,a[i]-1);j++) ans=(ans+dp[max(j+1,mx[i-1]+1)])%p;
		for(j=1;j<=i;j++) dp[j]=((j-1)*dp[j]+dp[j+1])%p;//滚动数组优化 
	}
	cout<<(ans+1)%p;//当前ans是多少方案比a小，ans+1后就是排名了 
	return 0;
}

by tangjiahua:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000007;
ll n,a[10010],mx[10010],dp[10010];
//dp[i,j]表示前i个人编号最大为j的合法序列数（需要滚动数组） 
//我们需要求字典序<原序列的合法序列数 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mx[i]=max(mx[i-1],a[i]);//记录前缀最大值 
		dp[i]=1;//初始化 
	}
	ll ans=1;//因为统计的是字典序<原序列的合法序列数，所以还要算上原序列 
	for(int i=n;i>=2;i--){//枚举从第i位开始与原序列不同 
		ans=(ans+(a[i]-1)*dp[max(mx[i-1],a[i]-1)])%mod;
		//枚举第i位选1~a[i]-1的方案数，后面可以随便选 
		for(int j=1;j<=i;j++)dp[j]=(dp[j]*j+dp[j+1])%mod;//更新数组，当最大编号为j时第i位可以选择1~j共j个或建一个新的队伍j+1 
	}
	cout<<ans;
	return 0;
}

by taojinghua+fuxuanyuan：

#include<iostream>
using namespace std;
typedef long long ll;
ll n,i,j,k,x,ans,p=1000007,mx[10005],a[10005],dp[10005];
int main(){
cin>>n;
for(i=1;i<=n;i++) dp[i]=1,cin>>a[i],mx[i]=max(mx[i-1],a[i]);//前缀最大值
for(i=n;i;i--){
//第i个人的队伍编号最多是mx[i-1]+1
ans=(ans+dp[mx[i-1]+1](a[i]-1)%p)%p;
/
原方法:for(j=1;j<=a[i]-1;j++)ans=(ans+dp[mx[i-1]+1])%p;
既然mx[i-1]+1为第i个人的队伍编号最大,则若a[i]-1>=mx[i-1]+1(即a[i]>mx[i-1]),此状态不合法,故for(j=1;j<=a[i]-1;j++)
同理,mx[i-1]+1也绝不小于j+1,故ans=(ans+dp[mx[i-1]+1])%p;
所以a[i]-1为可行个数,dp[mx[i-1]+1]为贡献队伍的情况个数。
可转化为ans=(ans+dp[mx[i-1]+1]*(a[i]-1)%p)%p;
*/
for(j=1;j<=i;j++) dp[j]=((j-1)*dp[j]+dp[j+1])%p;//滚动数组优化
}
cout<<(ans+1)%p;//当前ans是多少方案比a小，ans+1后就是排名了
return 0;
}