题解 | #计数#

基于组合数学的线性计数模型

1. 问题分析

本题是一个典型的受限序列填充计数问题。我们需要在保证序列单调不增（Monotonically Non-Increasing）的前提下，计算填充所有缺失位置（0）的方案数。

可以将问题分解为以下几个关键特征：

1. 锚点分割（Segmentation by Anchors）：序列中已知的非零数字充当了“锚点”。这些锚点将整个序列分割成若干个独立的区间。由于单调性的限制是局部的传递关系（），两个已知数字之间的填充方案仅取决于这两个数字的值以及中间0的个数，与其他区间的填充无关。
2. 独立性（Independence）：根据乘法原理，总方案数等于各个独立区间方案数的乘积。
3. 区间约束（Interval Constraints）：
   • 假设一段连续的0序列长度为 。
   • 该段左侧最近的非零数为 （若无，则隐含上界 ）。
   • 该段右侧最近的非零数为 （若无，则隐含下界 ）。
   • 问题转化为：在区间 中选择 个整数 ，使得 。

2. 算法：可重组合（Stars and Bars / Combinations with Repetition）

针对每一个被锚点 和 包围的长度为 的空白段，我们需要计算满足 的方案数。

数学推导：

1. 这等价于在整数集合 中选择 个数。
2. 允许重复选择（因为是不增，不是严格递减，即可以 ）。
3. 顺序无关性：一旦我们选定了 个数，为了满足单调不增的条件，这 个数在序列中的排列顺序是唯一的（必须从大到小排）。
4. 因此，问题转化为：从大小为 的集合中，可重复地选取 个元素的组合数。

公式： 根据可重组合公式（Multiset Coefficient），从 个元素中可重复选取 个元素的方案数为 。 代入本题变量：

• 可选值的个数
• 需选取的个数

特殊情况判断： 如果如果在原序列中存在相邻的（或是跨越0的）两个非零数 和 () 使得 ，这直接违反了单调不增的性质，方案数为 。

该算法避免了复杂的动态规划，利用了数论中的隔板法/可重组合思想，将问题转化为多个独立的组合数学子问题。

计算复杂度分析

时间复杂度：

其中 是序列长度， 是数值范围（本题为 ）。

1. 预处理阶乘（Precomputation）：我们需要计算组合数 。由于 很大，必须预处理阶乘及其模逆元。预处理范围需要覆盖组合数的上标，最大约为 。复杂度为线性的 。
2. 线性扫描（Linear Scan）：只需要遍历一次序列统计连续的0并计算每个区间的组合数。复杂度为 。
3. 组合数计算：每次计算耗时 。

空间复杂度：

1. 需要开数组存储阶乘表和逆元表，大小约为 。
2. 输入序列存储需要 。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;

struct Comb {
    vector<ll> fact;
    vector<ll> invFact;

    Comb(int n) {
        fact.resize(n + 1);
        invFact.resize(n + 1);

        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[n] = power(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    ll power(ll base, ll exp) const {
        ll res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1)
                res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    ll nCr(int n, int k) const {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    Comb comb(n + 1000);

    ll ans = 1;
    int lastVal = 1000;
    int cnt = 0;

    for (int x : a) {
        if (x == 0) {
            cnt++;
        } else {
            if (lastVal < x) {
                cout << "0\n";
                return 0;
            }
            int m = lastVal - x + 1;
            ll ways = comb.nCr(m + cnt - 1, cnt);
            ans = (ans * ways) % MOD;
            lastVal = x;
            cnt = 0;
        }
    }

    if (cnt > 0) {
        ll ways = comb.nCr(lastVal + cnt - 1, cnt);
        ans = (ans * ways) % MOD;
    }

    cout << ans << endl;
}