题解 | 计数

C++的自动取模类Z和组合数comb用的jiangly鸽鸽的模板，具体实现可以看后面的Python代码

#include <iostream>
#include <vector>
#include <cassert>

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}

template<int P>
struct MInt {
  int x;
  constexpr MInt() : x{} {}
  constexpr MInt(i64 x) : x{norm(x % getMod())} {}

  static int Mod;
  constexpr static int getMod() {
    if (P > 0) {
      return P;
    } else {
      return Mod;
    }
  }
  constexpr static void setMod(int Mod_) {
    Mod = Mod_;
  }
  constexpr int norm(int x) const {
    if (x < 0) {
      x += getMod();
    }
    if (x >= getMod()) {
      x -= getMod();
    }
    return x;
  }
  constexpr int val() const {
    return x;
  }
  explicit constexpr operator int() const {
    return x;
  }
  constexpr MInt operator-() const {
    MInt res;
    res.x = norm(getMod() - x);
    return res;
  }
  constexpr MInt inv() const {
    assert(x != 0);
    return power(*this, getMod() - 2);
  }
  constexpr MInt& operator*=(MInt rhs)& {
    x = 1LL * x * rhs.x % getMod();
    return *this;
  }
  constexpr MInt& operator+=(MInt rhs)& {
    x = norm(x + rhs.x);
    return *this;
  }
  constexpr MInt& operator-=(MInt rhs)& {
    x = norm(x - rhs.x);
    return *this;
  }
  constexpr MInt& operator/=(MInt rhs)& {
    return *this *= rhs.inv();
  }
  friend constexpr MInt operator*(MInt lhs, MInt rhs) {
    MInt res = lhs;
    res *= rhs;
    return res;
  }
  friend constexpr MInt operator+(MInt lhs, MInt rhs) {
    MInt res = lhs;
    res += rhs;
    return res;
  }
  friend constexpr MInt operator-(MInt lhs, MInt rhs) {
    MInt res = lhs;
    res -= rhs;
    return res;
  }
  friend constexpr MInt operator/(MInt lhs, MInt rhs) {
    MInt res = lhs;
    res /= rhs;
    return res;
  }
  friend constexpr std::istream& operator>>(std::istream& is, MInt& a) {
    i64 v;
    is >> v;
    a = MInt(v);
    return is;
  }
  friend constexpr std::ostream& operator<<(std::ostream& os, const MInt& a) {
    return os << a.val();
  }
  friend constexpr bool operator==(MInt lhs, MInt rhs) {
    return lhs.val() == rhs.val();
  }
  friend constexpr bool operator!=(MInt lhs, MInt rhs) {
    return lhs.val() != rhs.val();
  }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;

struct Comb {
  int n;
  std::vector<Z> _fac;
  std::vector<Z> _invfac;
  std::vector<Z> _inv;

  Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
  Comb(int n) : Comb() {
    init(n);
  }

  void init(int m) {
    if (m <= n) return;
    _fac.resize(m + 1);
    _invfac.resize(m + 1);
    _inv.resize(m + 1);

    for (int i = n + 1; i <= m; i++) {
      _fac[i] = _fac[i - 1] * i;
    }
    _invfac[m] = _fac[m].inv();
    for (int i = m; i > n; i--) {
      _invfac[i - 1] = _invfac[i] * i;
      _inv[i] = _invfac[i] * _fac[i - 1];
    }
    n = m;
  }

  Z fac(int m) {
    if (m > n) init(2 * m);
    return _fac[m];
  }
  Z invfac(int m) {
    if (m > n) init(2 * m);
    return _invfac[m];
  }
  Z inv(int m) {
    if (m > n) init(2 * m);
    return _inv[m];
  }
  Z binom(int n, int m) {
    if (n < m || m < 0) return 0;
    return fac(n) * invfac(m) * invfac(n - m);
  }
  Z permu(int n, int m) {
    if (n < m || m < 0) return 0;
    return fac(n) * invfac(n - m);
  }
} comb;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n;
  std::cin >> n;

  std::vector<int> a(n+2);
  for(int i = 1; i <= n; i++){
    std::cin >> a[i];
  }
  a[0] = 1000;
  a[n+1] = 1;

  Z dp = 1;
  int prev = a[0],next = a[n+1];
  int cnt = 0;
  for(int i = 1; i <= n+1; i++){
    if(a[i]){
      next = a[i];
      if(cnt){
        int len = prev - next + 1;
        dp *= comb.binom(cnt + len -1, len - 1);
        cnt = 0;
      }
      prev = a[i];
    }else{
      cnt++;
    }
  }

  std::cout << dp << "\n";
}

对于Python来说，同时预处理fac和invfac数组可能会MLE（补测了一下，并不会MLE，那我把同时预处理的代码放最下面），因此我们只预处理fac数组，invfac通过快速幂求逆元来求

import sys

input = lambda : sys.stdin.readline().strip()

P = 10 ** 9 + 7

fac = [0] * 1001001
fac[0] = 1
for i in range(1,1001001):
  fac[i] = fac[i - 1] * i % P

def inv(n):
  return pow(n, P - 2, P)

def C(n, m):
  inv1 = inv(fac[m])
  inv2 = inv(fac[n - m])
  return (fac[n] * inv1 % P) * inv2 % P

n = int(input())
a = [1000] + list(map(int,input().split())) + [1]

dp, pre, nxt, cnt = 1, a[0], a[-1], 0
for i in range(1,n+2):
  if a[i]:
    nxt = a[i]
    if cnt:
      siz = pre - nxt + 1
      dp = dp * C(cnt + siz - 1, siz - 1) % P
      cnt = 0
    pre = a[i]
  else:
    cnt += 1

print(dp)

同时预处理fac和invfac的Python代码

import sys

input = lambda : sys.stdin.readline().strip()

P = 10 ** 9 + 7

fac = [0] * 1001001
fac[0] = 1
for i in range(1,1001001):
  fac[i] = fac[i - 1] * i % P

def inv(n):
  return pow(n, P - 2, P)

invfac = [0] * 1001001
invfac[-1] = inv(fac[1001000])
for i in range(1001000, 0, -1):
  invfac[i - 1] = invfac[i] * i % P

def C(n, m):
  return (fac[n] * invfac[m] % P) * invfac[n-m] % P

n = int(input())
a = [1000] + list(map(int,input().split())) + [1]

dp, pre, nxt, cnt = 1, a[0], a[-1], 0
for i in range(1,n+2):
  if a[i]:
    nxt = a[i]
    if cnt:
      siz = pre - nxt + 1
      dp = dp * C(cnt + siz - 1, siz - 1) % P
      cnt = 0
    pre = a[i]
  else:
    cnt += 1

print(dp)