Codeforces 451E Devu and Flowers (组合数学+容斥+Lucas)

Devu wants to decorate his garden with flowers. He has purchasedn boxes, where the i-th box contains f_i flowers. All flowers in a single box are of the same color (hence they are indistinguishable). Also, no two boxes have flowers of the same color.

Now Devu wants to select exactly s flowers from the boxes to decorate his garden. Devu would like to know, in how many different ways can he select the flowers from each box? Since this number may be very large, he asks you to find the number modulo (10⁹ + 7).

Devu considers two ways different if there is at least one box from which different number of flowers are selected in these two ways.

Input

The first line of input contains two space-separated integersn and s (1 ≤ n ≤ 20,0 ≤ s ≤ 10¹⁴).

The second line contains n space-separated integersf₁, f₂, ...f_n (0 ≤ f_i ≤ 10¹²).

Output

Output a single integer — the number of ways in which Devu can select the flowers modulo(10⁹ + 7).

ExamplesInput

2 3
1 3

Output

Input

2 4
2 2

Output

Input

3 5
1 3 2

Output

Note

Sample 1. There are two ways of selecting 3 flowers: {1, 2} and {0, 3}.

Sample 2. There is only one way of selecting 4 flowers: {2, 2}.

Sample 3. There are three ways of selecting 5 flowers: {1, 2, 2}, {0, 3, 2}, and {1, 3, 1}.

题目链接：http://codeforces.com/problemset/problem/451/E

题目大意：n个盒子，第i个里有fi朵花，同盒的花都同色，每个盒子的花色都不同，求选s朵的方案

题目分析：非常典型的容斥题，首先sum朵花放到n个盒子里允许盒子为空的方案数通过隔板法是C(sum + n - 1, n - 1)，选s朵其实就相当于将s朵花放到个盒子里，但是每个盒子的花的数量是有限制的，这里做一下容斥即可，总方案数 - 一个盒子超出 + 两个盒子超出 -...，计算一个盒子超出的方案很简单，假设是第i个盒子，直接用sum-f[i]-1的值正常放就好，相当于先把f[i]+1个球丢到第i个盒子里，加1是因为允许不放，所以保证超出必须加1，剩下的那些可以放在第i个盒子，也可以不放，因为已经保证第i个超出了，其实和HDU 5201 一样，都是套路，考虑到数据范围，求组合数的时候需要Lucas定理搞一下，最后要注意答案累加的时候因为有个sign，结果可能为负，所以要加个MOD

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ll const MOD = 1e9 + 7;
int n;
ll s, f[25];

ll qpow(ll a, ll x) {
    ll res = 1;
    while(x) {
        if (x & 1) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        x >>= 1;
    }
    return res;
}

ll C(ll n, ll k) {  
    if(n < k) {
        return 0;
    }
    if(k > n - k) {  
        k = n - k;  
    }
    ll a = 1, b = 1;  
    for(int i = 0; i < k; i++) {  
        a = a * (n - i) % MOD;
        b = b * (i + 1) % MOD;
    }  
    return a * qpow(b, MOD - 2) % MOD;
}  

ll lucas(ll a, ll b) {
    if(b == 0) {
        return 1;
    }
    return C(a % MOD, b % MOD) * lucas(a / MOD, b / MOD) % MOD;
}

int main() {
    scanf("%d %I64d", &n, &s);
    for(int i = 0; i < n; i ++) {
        scanf("%I64d", &f[i]);
    }
    ll ans = 0;
    for(int i = 0; i < (1 << n); i ++) {
        ll sign = 1, sum = s;
        for(int j = 0; j < n; j ++) {
            if(i & (1 << j)) {
                sum -= (f[j] + 1);
                sign = -sign;
            }
        }
        if(sum >= 0) {
            ans = (MOD + ans % MOD + (sign * lucas(sum + n - 1, n - 1)) % MOD) % MOD;
        }
    }
    printf("%I64d\n", ans);
}

秒客网

Codeforces 451E Devu and Flowers (组合数学+容斥+Lucas)

相关文章