题解 | #一道计数题#

题目实际上是在求:

由常见生成函数式子可知：

令 $p=a_i+1p=a\_i+1$ 可得：

记 $t={\sum }_{i=1}^n{a}_{i}t=\backslash sum\_\{i=1\}^n\; a\_i$，所以可以推出最后所求为，再通过组合数斜线求和公式可得：

所以 $O(n+t)O(n+t)$ 求一个组合数即可。

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int mpow(int x , int y = MOD - 2) {
    int ret = 1;
    while (y) {
        if (y & 1) ret = 1ll * ret * x % MOD;
        x = 1ll * x * x % MOD;
        y >>= 1;
    }
    return ret;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);

    int N , m;
    cin >> N >> m;

    int u = m + N;

    int sum = 0;
    for (int i = 1 ; i <= N ; i++) {
        int x;
        cin >> x;
        sum += x;
        if (sum >= MOD) sum -= MOD;
    }

    if (m + N < N + sum) {
        cout << "0\n";
    } else {
        int ans = 1 , d = 1;
        for (int i = 1 ; i <= N + sum ; i++) {
            ans = 1ll * ans * (u - i + 1) % MOD;
            d = 1ll * d * i % MOD;
        }
        d = mpow(d);
        cout << 1ll * ans * d % MOD << endl;
    }
    return 0;
}