题目描述

难度分:$2300$

输入$n(1 \leq n \leq 20)$，$s(0 \leq s \leq 10^{14})$和长为$n$的数组$a(0 \leq a[i] \leq 10^{12})$。

你有$n$个盒子，第$i$个盒子装有$a[i]$朵颜色一样的花（无法区分）。此外，没有两个盒子中的花朵颜色相同。

从这些盒子中恰好选出$s$朵花的方案数是多少？模$10^9+7$。

输入样例$1$

2 3
1 3

输出样例$1$

2

输入样例$2$

2 4
2 2

输出样例$2$

1

输入样例$3$

3 5
1 3 2

输出样例$3$

3

算法

隔板法+容斥原理

记第$i$个盒子中取$x_i$束花，则有$x_1+x_2+…+x_n=s$成立，假设每个盒子中的花是无限的，那么这个问题就是求方程的非负数解个数。我们再做一个映射$y_i=x_i+1$，则有$y_1+y_2+…+y_n=s+n$。

此时求方程$x_1+x_2+…+x_n=s$的非负数解就等价于求方程$y_1+y_2+…+y_n=s+n$的正整数解，可以用隔板法求解，正整数解的个数为$C_{s+n-1}^{n-1}$。

而本题中还存在限制$x_i \leq a_i$，所以$y_i \leq a_i+1$，利用容斥原理来做。设$s_i$表示至少不满足$y_i \leq a_i+1$的解的数目，根据容斥原理，方案数应该为

$C_{s+n-1}^{n-1}-(s_1+s_2+…+s_n) + (s_{12}+s_{13}+…)-(s_{123}+s_{134}+…)+…$

如果第一个条件不满足，则我们先从盒子$1$中划分$a_1+1$束花出来，然后剩下的$s+n-1-(s_1+1)$个间隔插板$n-1$块，这样一来后面划分出来的$n$块就必须有一块和第一块合并才能保证总共是$n$块，第$1$个盒子拿出来的花就肯定大于$a_1+1$了，方案数为$C_{s+n-1-(a_1+1)}^{n-1}$。同理，如果前两个条件不满足，则先从盒子$1$中划分$a_1+1$束花出来，再从盒子$2$中划分$a_2+1$束花出来，剩下的$s+n-1-(a_1+1)-(a_2+1)$个间隔插板$n-1$块，方案数为$C_{s+n-1-(a_1+1)-(a_2+1)}^{n-1}$。

以此类推，通过这种方式计算上式，奇数个条件不满足是减去，偶数个条件不满足是加上。

复杂度分析

时间复杂度

容斥原理二进制枚举状态的时间复杂度为$O(2^n)$，对于每个状态需要遍历每一位，然后$O(n)$计算组合数来求取当前状态对答案的贡献。因此，整个算法的时间复杂度为$O(n2^n)$。

空间复杂度

除了输入的数组$a$，仅使用了有限几个变量，且整个算法并没有递归过程，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 20, MOD = 1e9 + 7;
int n;
LL m, denominator, A[N];

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

LL C(LL a, LL b) {
    if(a < b) return 0;
    LL numerator = 1;
    for(LL i = a; i > a - b; i--) {
        numerator = i % MOD * numerator % MOD;
    }
    return numerator * denominator % MOD;
}

int main() {
    scanf("%d%lld", &n, &m);
    for(int i = 0; i < n; i++) scanf("%lld", &A[i]);
    denominator = 1;
    for(int i = 1; i <= n - 1; i++) denominator = (LL)i * denominator % MOD;
    denominator = fast_power(denominator, MOD - 2, MOD);
    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 = (res + C(a, b)*sign) % MOD;
    }
    printf("%d", (res + MOD) % MOD);
    return 0;
}