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

思路

发现只需要将所有的空段找出来, 分别计算贡献

假设对于当前空段, 长度是 $t$ , 可以填的数字数量是 $h$

假设对于数字 $1$ 填了 $c_1$ 个, 数字 $2$ 填了 $c_2$ 个...

那么有

c_1 + c_2 + ... +c_h = t

发现每个 $c_i \ge 0$ , 将其转化 $\ge 1$ , 得到新的 $c_i = c_i + 1$

c_1 + c_2 + ... + c_h = h + t

这样就可以利用隔板法计算组合数, 要求将球的数量分为 $t$ 堆, 放置 $t - 1$ 个隔板方案数是 $C_{h + t - 1} ^ {t - 1}$

计算组合数可以用乘法逆元优化

实现代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e6 + 1010, MOD = 1e9 + 7;

int n;
int w[N];
vector<PII> v;
LL fact[M], infact[M];

LL q_pow(LL a, LL b, int MOD) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i < M; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        infact[i] = q_pow(fact[i], MOD - 2, MOD);
    }
}

LL C(LL a, LL b) {
    if (a < b) return 0;
    if (b == 0 || a == b) return 1;
    return fact[a] * infact[a - b] % MOD * infact[b] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    w[0] = 1000, w[n + 1] = 1;

    int j = 0;
    for (int i = 1; i <= n + 1; ++i) {
        if (w[i]) {
            v.push_back({j, i});
            j = i;
        }
    }

    LL ans = 1;
    for (auto [x, y] : v) {
        LL h = (y - 1) - (x + 1) + 1;
        LL t = w[x] - w[y] + 1;
        ans = ans * C(h + t - 1, h) % MOD;
    }

    ans = (ans % MOD + MOD) % MOD;
    cout << ans << '\n';
    return 0;
}