codeforce 258#E(lucas+容斥+结合）

codeforce 258#E(lucas+容斥+组合）

CF 451E

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

typedef long long ll;
const ll mod=1000000007;


ll qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }

    return ans;
}

ll C(ll m,ll n,ll p)
{
    if(n>m) return 0;
    if(m-n<n) n=m-n;
    ll s1=1,s2=1;
    for(ll i=0;i<n;i++){
        s1=s1*(m-i)%p;
        s2=s2*(i+1)%p;
    }
    return s1*qpow(s2,p-2,p)%p;
}

ll lucas(ll m,ll n ,ll p)     //求C(m,n) mod p
{
    if(!n) return 1;
    return C(m%p,n%p,p)*lucas(m/p,n/p,p)%p;
}

/*
数论Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。
描述为:
Lucas(n,m,p)=cm(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;
而
<费马小定理p为素数， a^(p-1)=1(mod p)->a^(p-2)=a^-1(mod p)->a^(p-2)是a mod p的逆；
cm(a,b)%p==a! / (b!*(a-b)!) mod p==a! * (b!*(a-b)!)^(p-2) mod p
也= (a!/(a-b)!) * (b!)^(p-2)) mod p
这里，其实就是直接求 (a!/(a-b)!) / (b!) mod p
由于 (a/b) mod p = a * b^(p-2) mod p
*/

int n;
ll s,f[25];

ll solve()
{
    ll ans=0;
    for(int i=0;i<(1<<n);i++){     //2^n枚举，即二进制枚举；
        ll sign=1,sum=s;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                sum-=f[j]+1;
                sign*=-1;
            }
        }
        if(sum<0) continue;
        ans+=sign*lucas(sum+n-1,n-1,mod);  //容斥原理
        ans%=mod;
    }

    return (ans+mod)%mod;
}

int main()
{
    while(scanf("%d%I64d",&n,&s)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%I64d",f+i);
        printf("%I64d\n",solve());
    }

    return 0;

}