C++(g++ 7.5.0) 解法, 执行用时: 294ms, 内存消耗: 484K, 提交时间: 2022-08-04 20:00:04

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Mod=1e9+7;
int N; ll M,f[22],ans;
ll qpow(ll a,ll x)
{
    ll res=1; a%=Mod;
    while(x){
        if(x&1LL) res=res*a%Mod;
        a=a*a%Mod;
        x>>=1;
    }   return res;
}
ll Com(ll a,ll b)
{
    ll res=1,fm=1,fz=1;
    if(a-b<b) b=a-b;
    for(int i=1;i<=b;i++){
        fm=fm*i%Mod;
        fz=fz*(a-i+1)%Mod;
    }
    res=fz*qpow(fm,Mod-2)%Mod;
    return res;
}
ll Lucas(ll a,ll b)
{
    if(b==0) return 1;
    return Lucas(a/Mod,b/Mod)*Com(a%Mod,b%Mod)%Mod;
}
void solve()
{
    for(int i=0;i<(1<<N);i++){
        ll sig=1,sum=M;
        for(int j=0;j<N;j++){
            if((1<<j)&i) sum-=(f[j]+1),sig*=-1;
        }
        if(sum<0) continue;
        ans=(ans+sig*Lucas(N+sum-1,N-1))%Mod;
    }
}
int main()
{
    scanf("%d%lld",&N,&M);
    for(int i=0;i<N;i++)
        scanf("%lld",&f[i]);
    solve();
    printf("%lld\n",(ans%Mod+Mod)%Mod);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 244ms, 内存消耗: 484K, 提交时间: 2020-10-06 17:10:39

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long a[22],m,ans=0;
int inv[22],n;
int power(int a,int b){
	int c=1;
	while(b){
		if(b&1)
		c=(long long)c*a%mod;
		a=(long long)a*a%mod;
		b/=2;
	}
	return c;
}
int C(long long y,int x){
	if(y<0||x<0||y<x)
	return 0;
	y%=mod;
	if(y==0||x==0)
	return 1;
	int ans=1;
	for(int i=0;i<x;i++)
	ans=(long long)ans*(y-i)%mod;
	for(int i=1;i<=x;i++)
	ans=(long long)ans*inv[i]%mod;
	return ans;
	
}
int main()
{
	for(int i=1;i<=20;i++)
	inv[i]=power(i,mod-2);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int x=0;x<1<<n;x++){
		if(x==0)
		ans=(ans+C(n+m-1,n-1))%mod;
	else{
		long long t=n+m;
		int p=0;
		for(int i=0;i<n;i++){
			if(x>>i&1){
				p++;
				t-=a[i+1];
			}
		}
		t-=p+1;
		if(p&1){
			ans=(ans-C(t,n-1))%mod;
		}
		else {
			ans=(ans+C(t,n-1))%mod;
		}
	}
    }
	cout << (ans+mod)%mod << endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 116ms, 内存消耗: 476K, 提交时间: 2023-03-16 18:01:01

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,s,jc=1,m[25],ans;
ll qpow(ll a,ll b,ll mod){
	ll ans=1;
	a%=mod;
	while(b){
		if(b&1)	ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
ll C(ll i){
	ll ans=1;
	for(ll j=s-i+1;j<=s-i+n-1;j++)	ans=j%mod*ans%mod;
	return ans*jc%mod;
}
void dfs(int pos,ll xishu,ll zhishu){
	if(pos==n){
		if(zhishu<=s)
			ans=((ans+xishu*C(zhishu)%mod)%mod+mod)%mod;
		return ;
	}
	dfs(pos+1,xishu,zhishu);
	dfs(pos+1,-xishu,zhishu+m[pos+1]+1);
}
int main(){
	scanf("%lld%lld",&n,&s);
	for(int i=2;i<n;i++)	jc*=i;
	jc=qpow(jc,mod-2,mod);
	for(int i=1;i<=n;i++)	scanf("%lld",&m[i]);
	dfs(0,1,0);
	printf("%lld\n",ans);
	return 0;
}