算法分析

• 假设任意个盒子都有无限个的话，等价于x1 + x2 + x3 + .. + xk = m (xi >= 0)
• 设yi = xi + 1 上式等价于 y1 + y2 + … + yk = m + k (y1 > 0)经典隔板法C(m + k - 1, k - 1)
• 但是这道题存在n个限制 根据容斥原理的套路这道题的做法就是总方案数 减去 至少不满足 一个限制的方案数 加上至少不满足两个限制的方案数 以此类推
• 假如第一个限制为a1 那么至少不满足a1的个数为 ，我先从第一个盒子选出a1 + 1 个再在 剩下的选择盒子中选出m个数，方案数为C(m + k - 1 - (a1 + 1), k - 1) 依次类推时间复杂度为O(2^n)

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 20, mod = 1e9 + 7;
LL A[N];

int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1)res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

LL C(LL a, LL b)
{
    if(a < b)return 0;
    LL up = 1, down = 1;
    for(LL i = a, j = 1; j <= b; j ++, i --)
    {
        up = i % mod * up % mod;
        down = (LL)down * j % mod;
    }
    return (LL)up * qmi(down, mod - 2) % mod;
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    cin >> A[i];
    LL res = 0;
    for(int i = 0; i < 1 << n; i ++)
    {
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for(int j = 0; j < n; j ++)
            if(i >> j & 1)
            {
                sign *= -1;
                a -= A[j] + 1;
            }
        res = ((LL)res + sign * C(a, b)) % mod;
    }
    cout << (res + mod) % mod << endl;
    return 0;
}