题目传送门
题目大意： 现在有 n n n 种花，第 i i i 种花有 f i f_i fi 个，现在要选出 s s s 朵花，问多有少种不同的选法。
这是一个裸的多重集组合数问题。
知道了计算公式之后，就很好做了。
因为 n n n 十分小，我们可以直接大力枚举有哪些花是拿多了的，不妨枚举一个 i i i，枚举范围是 [ 0 , 2 n − 1 ] [0,2^n-1] [0,2n−1]，我们看 i i i 的二进制数，假如 i i i 的第 j j j 位为 1 1 1，那么就是第 j j j 种花拿多了。
假设此时枚举出来有 p 1 , p 2 , ⋯ , p k p_1,p_2,\cdots,p_k p1,p2,⋯,pk 这些种类的花拿多了，那么产生的贡献就是： ( − 1 ) k C n + s − 1 − ∑ i = 1 k ( f p i + 1 ) n − 1 (-1)^k C_{n+s-1-\sum_{i=1}^k (f_{p_i}+1)}^{n-1} (−1)kCn+s−1−∑i=1k(fpi+1)n−1
因为下面的部分可能很大，所以需要用卢卡斯定理来算。
而且因为 n − 1 n-1 n−1 和 n + s − 1 − ∑ i = 1 k ( f p i + 1 ) n+s-1-\sum_{i=1}^k (f_{p_i}+1) n+s−1−∑i=1k(fpi+1) 相比太小了，所以代码中采用了这样的组合数计算方式： C x y = x ! y ! ( x − y ) ! = ( x − y + 1 ) × ( x − y + 2 ) × . . . × x y ! C_x^y=\frac {x!}{y!(x-y)!}=\frac {(x-y+1)\times(x-y+2)\times...\times x} {y!} Cxy=y!(x−y)!x!=y!(x−y+1)×(x−y+2)×...×x
注意，除以 y ! y! y! 需要用逆元。
代码如下：
#include <cstdio> #include <cstring> #define ll long long #define mod 1000000007 int n; ll s,f[110],ans=0; ll ksm(ll x,ll y) { ll re=1,tot=x; while(y) { if(y&1)re=re*tot%mod; tot=tot*tot%mod; y>>=1; } return re; } #define inv(x) ksm(x,mod-2) ll C(ll x,ll y) { if(y>x)return 0; if(y>x-y)y=x-y; ll sum1=1,sum2=1; for(int i=x-y+1;i<=x;i++) sum1=sum1*i%mod; for(int i=2;i<=y;i++) sum2=sum2*i%mod; return sum1*inv(sum2)%mod; } ll lucas(ll x,ll y) { if(y==0)return 1; return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod; } int main() { scanf("%d %lld",&n,&s); for(int i=0;i<n;i++) scanf("%lld",&f[i]); for(int i=0;i<(1<<n);i++) { int f1=1; ll sum=n+s-1; for(int j=0;j<n;j++) { if((i&(1<<j))>0) { f1*=-1; sum-=f[j]+1; } } if(sum>=0)ans=(ans+f1*lucas(sum,n-1)+mod)%mod; } printf("%lld",ans); }