题解 | #计数#_牛客博客

题目目标在于找到各个连续0序列，算出计数贡献后乘起来。因此，核心的任务在于，对于一个[l,0,0,...,0,r]的序列，如何求出其计数贡献。

我们将0的个数记为 $k$ ，形式化地，问题为：

$k$ 个数的数列 $\{b_k\}$ 满足以下表达式，求符合的 $\{b_k\}$ 数量 $L\ge b_1\ge b_2\ge \cdots \ge b_k \ge R\\$

这个事情的需求有两个：

单调不减
整个数列在 $[R,L]$ 内

如果我们要手动做这么个事情，有两种思考方式：从1入手考虑和从2入手考虑。

如果优先考虑单调不减

由 $L$ 得到 $b_1$ 范围，再由 $b_1$ 得到 $b_2$ 范围，这样计算方案是很困难的，需要 $k-1$ 个求和

如果优先考虑范围

如果我们选出范围符合的数列，如何得到单调不减？很简单，排序即可。

换句话说，我们（可重复）选出 $k$ 个范围符合的数，排序后就是一个解。这个排序是不影响计数的，换句话说，两个排序后相同的选择只贡献一个计数，这是符合题意的。因此，上述需要的构造和可重复选出 $k$ 个范围符号的数的计数结果相同（方案一一对应）。

因此，问题转变为：

取值集合 $\{R, R+1,\cdots,L\}$ 可重复选出 $k$ 个数的方案个数。

由于这个集合里具体的元素是什么，并不影响结果，我们直接记为 $S$ ，其元素个数为 $s:=L-R+1$ .

对于这个问题有经典的转换方法：这个问题等价于，将 $k$ 个球可重复放入 $s$ 个盒子的方案数

而球放盒子的问题可以等价于，球被隔板分割的问题，那么就等价到 $k$ 个球被 $s-1$ 个隔板分割(允许隔板间为空)，由于允许隔板之间为空，不能直接认为是 $C_{k+1}^{s-1}$ ，因为插入一次隔板后会产生新的间隙。

一个比较巧妙的思路是考虑最终物体：分割完，最终有 $k+s-1$ 个东西，选择其中 $k$ 个作为球，得到方案数为 $C_{k+s-1}^k$ .

因此计算回去就得到，先前的问题的答案 $C_{k+l-r}^{k}$

如何计算组合数

阶乘一般预处理来算；模意义下除法需要使用乘法逆元，可以用快速幂以及费马小定理得到。预处理的时间复杂度为 $O(n)$ ，计算一次组合数的时间复杂度为 $O(\log (k+l-r))\le O(\log n)$ ，至此已能AC本题。

我们介绍另外一种优秀的算法，可以在 线性时间内求 $1,2,\cdots, n$ 的乘法逆元，因而能在线性时间内预处理出各个阶乘的逆元。我们先给出结论： $\mathrm{inv}[1]=1,\quad \mathrm{inv}[i]=(p-\lfloor p/i\rfloor)\cdot \mathrm{inv}[p\bmod i] \bmod p\\$

证明：由欧几里得除法：
$p = (p \bmod i) + \lfloor p/i \rfloor \cdot i\\$
两边乘以 $\operatorname{inv}[i]$ ，在模 $p$ 下：
$0 \equiv (p \bmod i)\operatorname{inv}[i] + \lfloor p/i \rfloor\\$
移项：
$(p \bmod i)\operatorname{inv}[i] \equiv -\lfloor p/i \rfloor\\$
再乘 $\operatorname{inv}[p \bmod i]$ ：
$\operatorname{inv}[i] \equiv - \lfloor p/i \rfloor \cdot \operatorname{inv}[p \bmod i] \pmod p\\$

参考代码

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

// l cnt个0 r 相当于{r,r+1,...,l}可重复选cnt个数字即可，自动排序后放入
// 取值集合共有l-r+1=:s个元素，可重复选k个相当于s个盒子，拿k个球放,代表对应盒子的权重
// 这又等价于，k个球拿s-1个挡板分割（但需要注意，挡板可以相邻，挡板插入后空隙会变多），因此，最终分割后有k+s-1个东西，选择k个作为球，答案为C(k+s-1,k) = C(l-r+k,k)
// 由于取模，可以阶乘预处理+逆元预处理

const int M = 1e9 + 7;
const int MAXK = 1e6 + 1000;
int fac[MAXK];
int inv[MAXK];
int facInv[MAXK];
// remark: 实际用到r-l+k<k<n，最多在1e6

void pre() {
    fac[0] = 1, fac[1] = 1;
    facInv[0] = 1, facInv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAXK; i++) {
        fac[i] = 1LL * fac[i - 1] * i % M;
        inv[i] = 1LL * (M - M / i) * inv[M % i] % M;
        facInv[i] = 1LL * facInv[i - 1] * inv[i] % M;
    }
}

inline long long binomial(int n, int m) {
    assert(n >= m);
    return (1LL * fac[n] * facInv[m]) % M * facInv[n - m] % M;
}

inline long long count(int l, int r, int k) {
    return binomial(l - r + k, k);
}

long long solve(int n) {
    
    vector<int> a(n);
    for (auto& num : a) cin >> num;
    

    long long ans = 1;

    int l = 1000;
    for (int i = 0; i < n; i++) {
        if (a[i] != 0) {
            l = a[i];
            continue;
        }

        int cnt = 0;
        int r = 1;
        while (i < n && a[i] == 0) {
            cnt++;
            i++;
        }
        if (i < n) r = a[i];
        ans = ans*count(l, r, cnt)%M;
        i--;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int n;
    cin >> n;
    pre();
    cout << solve(n);
}