codeforces 451E Devu and Flowers(容斥原理，Lucas，dfs，隔板法)

╰+哭是因爲堅強的太久メ 2022-06-09 13:27 55阅读 0赞

E. Devu and Flowers

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Devu wants to decorate his garden with flowers. He has purchased *n* 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 (109 + 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 integers *n* and *s* (1 ≤ *n* ≤ 20, 0 ≤ *s* ≤ 1014).

The second line contains *n* space-separated integers *f*1, *f*2, ... *f**n* (0 ≤ *f**i* ≤ 1012).

Output

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

Examples

input

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\}.

**题意**：给你n个箱子，第i个箱子中有fi朵花，要从中选出一共s朵花，问你有多少种方法。在每个箱子中选的花的个数一样的话算同一种方案。

**思路**：首先我们要利用隔板法的思想，将s朵花分在n个箱子中一共有C(s+n-1,n-1)种情况，然后我们再来考虑这其中不符合题目条件的情况，那就是某些箱子中放的花朵超出限制了的情况。假设第i个箱子超出了限制，那么第i个箱子肯定就有fi+1朵花，剩下的s-fi-1朵花要再放入n个箱子中，所以这时的情况总数为C(s-fi-1+n-1，n-1)。很明显，此处要用容斥原理。n个箱子超限制的情况数，n为奇就减去，为偶就加上，然后计算组合数的时候因为数据很大所以要用lucas定理。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100000007;
    const int MOD = 1e9+7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    LL quick_mod(LL a, LL b, LL c)  
    {
    	LL ans = 1;
    	while (b)
    	{
    		if (b % 2 == 1)
    			ans = (ans*a) % c;
    		b /= 2;
    		a = (a*a) % c;
    	}
    	return ans;
    }
    
    
    LL C(LL n, LL k,LL p) {
    	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) % p;
    		b = b * (i + 1) % p;
    	}
    	return a * quick_mod(b, p - 2,p) % p;
    }
    
    LL lucas(LL a, LL b,LL p)
    {
    	if (b == 0)
    		return 1;
    	return C(a % p, b % p,p) * lucas(a / p, b / p,p) % p;
    }
    
    LL a[25];
    LL ans;
    LL n, s;
    
    void dfs(int flag, LL num, LL sum)
    {
    	if (num == n)
    	{
    		if (sum > s||sum==0)
    			return;
    		if (flag)
    			ans = (ans+lucas(s - sum + n - 1, n - 1,MOD)%MOD+MOD)%MOD;
    		else
    			ans = (ans-lucas(s - sum + n - 1, n - 1,MOD)%MOD+MOD)%MOD;
    		return;
    	}
    	dfs(flag, num + 1, sum);
    	dfs(flag ^ 1, num + 1, sum + a[num + 1] + 1);
    }
    
    int main()
    {
    	scanf("%lld%lld", &n, &s);
    	for (int i = 1; i <= n; i++)
    		scanf("%lld", &a[i]);
    	ans = lucas(s + n - 1, n - 1,MOD);
    	dfs(1, 0, 0);
    	printf("%lld\n", ans);
    }