文远知行杯广东工业大学第十六届程序设计竞赛 J 一道计数题

题目描述

https://ac.nowcoder.com/acm/contest/30896/J

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在需要计算对于所有满足条件的序列 $b_i$ $\prod_{i=1}^n\binom{b_i}{a_i}$ 的累加和，序列 $b_i$ 满足的条件为序列 $b$ 只包含自然数且长度为 $n$，序列 $b_i$ 中所有数的和小于等于 $m$

$n\le 5000,a_i\le 2000,m\le 10^9$

Solution

考虑生成函数，我们令 $F_k(x)=\sum_{i=0}^\infty\binom{i}{a_k}x^k$，容易得到答案就是 $\sum_{k=0}^m[x^k]\prod_{i=1}^nF_i(x)$，注意到 $F_i(x)$ 的形式还可以继续化简，根据 $\frac{1}{(1-x)^k}=\sum_{i=0}^\infty\binom{i+k-1}{k-1}x^i$，我们可以得到 $F_k(x)=\frac{x^{a_k}}{(1-x)^{a_k+1}}$

那么 $ans=\sum_{k=0}^m[x^k]\frac{x^{\sum_{i=1}^na_i}}{(1-x)^{n+\sum_{i=1}^na_i}}$，我们令 $t=\sum_{i=1}^na_i$，那么 $ans=\binom{m+n}{n+t}$

#include <iostream>
#define maxn 5010
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

int n, m, a[maxn];

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

    cin >> n >> m; int sum = 0;  
    for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
    if (sum > m) return cout << 0 << "\n", 0;
    ll ans = 1, mul = 1; 
    for (int i = 1; i <= n + sum; ++i) {
        ans = ans * (m - sum + i) % p;
        mul = mul * i % p; 
    } cout << ans * pow_mod(mul, p - 2) % p << "\n";
    return 0;
}