C++14(g++5.4) 解法, 执行用时: 139ms, 内存消耗: 16012K, 提交时间: 2019-09-16 21:08:25

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,maxn=1e6+1;
typedef long long ll;
ll f[maxn],a[maxn];
ll quick(ll a,ll b)
{
    ll r=1;
    for(;b;b>>=1,a=a*a%mod)
    if(b&1) r=r*a%mod;
    return r;
}
void init()
{
    f[0]=1;
    for(int i=1;i<maxn;++i)
    f[i]=(f[i-1]*i)%mod;
}
ll c(ll a,ll b)
{
    return f[a]*quick(f[b],mod-2)%mod*quick(f[a-b],mod-2)%mod;
}
int main()
{
    int n;
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    ll ans=1,cnt=0,pre=1000;a[n+1]=1;
    for(int i=1;i<=n+1;++i)
    {
        if(a[i]==0) cnt++;
        else{
            ll size=pre-a[i]+1;
            ans=ans*(c(size+cnt-1,cnt)%mod)%mod;
            cnt=0;
            pre=a[i];
        }
    }
    printf("%lld\n",ans);
}

C++(g++ 7.5.0) 解法, 执行用时: 199ms, 内存消耗: 15964K, 提交时间: 2022-11-09 21:10:21

#include<stdio.h>
#define ll long long
const ll p=1e9+7;
const ll N=1e6+7;
ll inv[N],a[N];
ll c(int n,int m)
{
	if(n<m) return 0;
    ll ans=1;
    for(ll i=1;i<=m;i++)
    ans=ans*((n-i+1)%p)%p*inv[i]%p;
    return ans;
}
int main()
{
    ll ans=1,last=1000,z,n; /*z为一段连续空的前段点，last为一段连续空的第一个数的大小*/
    scanf("%lld",&n);
    inv[1]=1;
    for(ll i=2;i<N;i++)
    inv[i]=inv[p%i]*(p-p/i)%p;
    for(ll i=1;i<=n;i++)
    {
       scanf("%lld",&a[i]);
       if(a[i])
       {
          (ans*=c(last-a[i]+i-z-1,i-z-1))%=p;
          last=a[i];
          z=i; 
       }
    }
    (ans*=c(last-1+n-z,n-z))%=p;
    printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 196ms, 内存消耗: 23908K, 提交时间: 2019-09-13 20:11:03

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long 
using namespace std;
const ll XJQ=1e9+7,N=2e6+100;
ll num[N],n,ans=1,last=1000,z,inv[N];
ll C(ll n,ll m)
{
	if(n<m) return 0;
	ll ans=1;
	for(ll i=1;i<=m;i++)
		ans=ans*((n-i+1)%XJQ)%XJQ*inv[i]%XJQ;
	return ans;
}
int main()
{
	scanf("%lld",&n);
	inv[1]=1;
	for(ll i=2;i<=N;i++)
		inv[i]=inv[XJQ%i]*(XJQ-XJQ/i)%XJQ;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&num[i]);
		if(num[i]){
			(ans*=C(last-num[i]+i-z-1,i-z-1))%=XJQ;
			last=num[i];z=i;
		}
	}
	(ans*=C(last-1+n-z,n-z))%=XJQ;
	printf("%lld",ans);
}