题目描述

blablabla

样例

blablabla

算法1

$O(2^n)$

时间复杂度分析：n很小，可以看做常数，外层循环2^n

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define int long long
typedef long long ll;

const int mod=1e9+7;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int n,m,a[25],inv[25];

template<typename T> inline void read(T &x){
    x=0;char f=1,c=getchar();
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

int qpow(int x,int p){
    int ans=1;
    for(;p;p>>=1){
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
    }
    return ans;
}

int C(int n,int m){
    if(n<0||n<m) return 0;
    n%=mod;
    if(!n||!m) return 1;
    int ans=1;
    go(i,0,m-1) ans=ans*(n-i)%mod;
    go(i,1,m) ans=ans*inv[i]%mod;
    return ans;
}

signed main(){
    //freopen("input.txt","r",stdin);
    read(n),read(m);
    inv[0]=1;
    go(i,1,n) inv[i]=qpow(i,mod-2);
    go(i,1,n) read(a[i]);
    int ans=0;
    for(int i=0;i<(1<<n);++i){
        if(!i){
            ans=(ans+C(n+m-1,n-1))%mod;
            continue;
        }
        int t=n+m-1,cnt=0;
        go(j,0,n-1){
            if(i&(1<<j)){
                t-=a[j+1];++cnt;
            }
        }
        t-=cnt;
        if(cnt&1) ans=(ans-C(t,n-1))%mod;
        else ans=(ans+C(t,n-1))%mod;
    }
    ans=(ans+mod)%mod;
    printf("%lld",ans);
    return 0;
}