[CF 451E] Devu and Flowers

作法：

簡單來說就是要問滿足$a_1+...+a_n=s$的$n$元組$(a_1,...,a_n)$的個數，並且$a_i\leq f_i$。記「滿足$a_i>f_i$且總和為$s$的$n$元組集合」為$A_i$，那麼所求就會是「總和為$s$的$n$元組」個數扣掉$|A_1\bigcup ... \bigcup A_n|$，因此可以考慮用排容原理。首先看所求的第一項，直接用排列組合的公式可以得到等於$C_{n-1}^{n+s-1}$，這東西直接算就可以了。接下來要考慮$A_i$的部份，我們想要知道好幾個$A_i$交集起來的大小為多少。假設現在我們要算$|A_{c_1}\bigcap ... \bigcap A_{c_r}|$，那麼就是對於每個$i$，都有$a_{c_i}>f_{c_i}$，因此我們先把$s$分給$a_{c_1},...,a_{c_r}$各$f_{c_1}+1,...,f_{c_r}+1$個，剩下再用排列組合的公式算就可以了。因此排容的過程就可以用個 DFS 來做，詳細可以參考 code 比較清楚。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=20 ;
 
LL power(LL x,int n)
{
    if(n<=1) return n ? x : 1 ;
    LL t=power(x,n/2) ;
    if(n%2) return (t*t%MOD)*x%MOD ;
    else return t*t%MOD ;
}
LL inv(int x)
{
    return power(x,MOD-2) ;
}
 
LL fac[maxn],ifac[maxn] ;
LL C(LL n,int m)
{
    n%=MOD ;
    if(n<m) return 0 ;
    LL ret=1 ;
    for(int i=0;i<m;i++) ret=ret*(n-i)%MOD ;
    return ret*ifac[m]%MOD ;
}
 
LL a[maxn],ans ;
int n ;
void dfs(int x,LL s,int mul)
{
    if(x==n){ans=(ans+mul*C(s+n-1,n-1))%MOD ; return ;}
    dfs(x+1,s,mul) ;
    if(s>a[x]) dfs(x+1,s-a[x]-1,-mul) ;
}
 
main()
{
    for(int i=0;i<maxn;i++) fac[i]= (i?fac[i-1]*i%MOD : 1) , ifac[i]=inv(fac[i]) ;
    LL s ; scanf("%d%lld",&n,&s) ;
    for(int i=0;i<n;i++) scanf("%lld",&a[i]) ;
    dfs(0,s,1) ;
    printf("%lld\n",(ans+MOD)%MOD) ;
}