题解 | #Devu and Flowers#

链接： https://ac.nowcoder.com/acm/contest/24710/B

分析：

$F_i(x)=1+x+x^2+\mathrm{.}\mathrm{.}\mathrm{.}+x^{f_i}=(1-x^{f_i+1})\mathrm{/}(1-x)F\_i(x)=1+x+x^2+...+x^\{f\_i\}=(1-x^\{f\_i+1\})/(1-x)$

$F(x)={\prod }_{i=1}^n{F}_i(x)=\frac{{\prod }_{i=1}^n(1-x^{f_i+1})}{(1-x{)}^n}F(x)=\backslash prod\_\{i=1\}^n\{F\_i(x)\}=\backslash frac\{\backslash prod\_\{i=1\}^n(1-x^\{f\_i+1\})\}\{(1-x)^n\}$

假设$A(x)=\mathrm{上}\mathrm{部},F(x)=\frac{A(x)}{(1-x{)}^n}A(x)=上部,\; F(x)=\backslash frac\{A(x)\}\{(1-x)^n\}$

$[x^s]F(x)={\sum }_{i=0}^s[x^i]A(x)\times [x^{s-i}]\frac{1}{(1-x{)}^n}[x^s]F(x)=\backslash sum\_\{i=0\}^\{s\}\{[x^i]A(x)\; \backslash times\; [x^\{s-i\}]\backslash frac\{1\}\{(1-x)^n\}\}$

$[x^{s-i}]\frac{1}{(1-x{)}^n}=\left(\genfrac{}{}{0px}{}{s-i+n-1}{s-i}\right)[x^\{s-i\}]\backslash frac\{1\}\{(1-x)^n\}=\{\{s-i+n-1\}\; \backslash choose\; \{s-i\}\}$

由于足够小，所以我们的A(x)直接通过搜索来求即可，然后预处理组合数。

const ll mod=1e9+7;
ll a[30]={0};
ll inv[30]={0};
ll jc[30]={0};
map<ll,ll> mp;
///把每一个指数的值给算出来了,[k,v]表示v*(x^k)
int n;
void dfs(int u,int ll x,bool zf){
    if(u==n+1){
        if(zf)mp[x]--;
        else mp[x]++;
        return;
    }
    dfs(u+1,x,zf);
    dfs(u+1,x+a[u]+1,zf^1);
}
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b%2==1){
            ans*=a;
        }
        ans%=mod;
        a*=a;
        a%=mod;
        b>>=1;
    }
    return ans;
}
ll C(ll n,ll m){
    ll ans=inv[n];
    for(int i=1;i<=n;i++){
        ans*=(m-i+1)%mod;
        ans%=mod;
    }
    return ans;
}
int main(){
    n=read();
    ll s=read();
    for(int i=1;i<=n;i++){a[i]=read();}
    jc[0]=1;
    for(int i=1;i<=22;i++){
        jc[i]=jc[i-1]*i%mod;
    }
    inv[22]=qpow(jc[22],mod-2);
    for(int i=21;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
    dfs(1,0,0);
    ll ans=0;
    for(auto [k,v]:mp){
        if(k>s)break;
        ans+=((v%mod+mod)%mod*(C(n-1,s-k+n-1)));
        ans%=mod;
    }
    writeln(ans);
}