(ARC_110_D) 二项式系数很有趣

题解

题意

形式化题意

给定长度为 N 的非负整数序列 A₁, A₂, …, A_N。

考虑所有长度为 N 的非负整数序列 B₁, B₂, …, B_N，满足 Σᵢ₌₁ᴺ Bᵢ ≤ M。

对于每个这样的序列 B，计算乘积：

∏ᵢ₌₁ᴺ C(Bᵢ, Aᵢ)

其中 C(n, k) 表示组合数（当 k > n 时规定为 0）。

求所有满足条件的序列 B 对应的乘积之和，并对 10⁹ + 7 取模。

数据范围

• 1 ≤ N ≤ 2000
• 1 ≤ M ≤ 10⁹
• 0 ≤ Aᵢ ≤ 2000

解法

又是一道并非美妙的组合数学题目。

首先我们先不管如何得到一个序列$B$,而是直接考虑如何得到$\prod_{i=1}^n \tbinom{B_i}{A_i}$

我们发现这个累乘是个乘法原理，可以看成选择有先后顺序。

根据组合数的意义，我们可以把这个式子看成有很多组小球，而小球总数不超过$m$个，然后依次在每组小球中选取$A_i$个小球的方案数。

但是要怎么分配每组小球球的数量呢？我们发现我们已知每组选取的小球是固定的，那么我们可以考虑将选球等价转化成在每组小球中放球。

我们已知小球总数不能超过$m$那么我们放的球的总数就不能超过$m-\sum_{i=1}^{n}A_i$而每一组小球中有$A_i+1$个空隙可以放球。

那么就一共有$\sum_{i=1}^n A_i+n$个空隙。

但是我们放的球的总数是不确定的啊，而且$m$太大直接枚举会超时。而我们要做到是将每种方案加起来，也就是说我们可以把这些情况一起考虑

于是我们可以考虑一个方式，我们额外开一个空隙，放那些没放的球。

那么问题就被转化成$m-\sum_{i=1}^n A_i$个小球放在$\sum_{i=1}^{n} A_i+n+1$个空隙中的方案数。

很明显的一个插板法，那么一共有$\sum_{i=1}^n A_i+n$个板，然后有$m+n$个位置放板。

那么这个题就是求

$$\dbinom{m+n}{\sum_{i=1}^n A_i+n}$$

好了这个题做完了

代码

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const int N=6e6+10;
ll n,a[N],m;
ll sum;
ll inv[N];
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    ll ans=1;
    if(m-sum<0)
    {
        cout<<0<<'\n';
        return 0;
    }
    for(ll i=m+n;i>m-sum;i--) ans=ans*i%mod;
    inv[0]=0,inv[1]=1;
    for(ll i=2;i<=sum+n;i++)
    {
        inv[i]=(-1ll*mod/i%mod*inv[mod%i]%mod+mod)%mod;
        ans=ans*inv[i]%mod;
    }                               
    cout<<ans<<'\n';
    return 0;
}