题解 | 计数

我讨厌数学，一道组合数的题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int mx=1e6+1000;
int fac[mx+1];
int fastpow(int x,int p){
    int ans=1;
    while(p){
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans%mod;
}
int inv(int x){
    return fastpow(x,mod-2);
}
int c(int a,int b){
    return fac[a]*inv(fac[b])%mod*inv(fac[a-b])%mod;
}
void solve(){
    int n;cin>>n;
    vector<int> a(n+2);
    a[0]=1000,a[n+1]=1;
    for(int i=1;i<=n;i++) cin>>a[i];
    int r=0;
    int ans=1;
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            r=i+1;
            while(a[r]==0){
                r++;
            }
            int l=r-i;
            int cnt=abs(a[r]-a[i-1])+1;
//             cout<<l<<" "<<cnt<<" ";
//             cout<<c(cnt+l-1,cnt-1)<<" ";
            ans=ans*c(cnt+l-1,cnt-1)%mod;
            i=r-1;
        }
    }
    cout<<ans%mod;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    fac[0]=1;
    for(int i=1;i<=mx;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}