题目链接：http://codeforces.com/contest/451/problem/E 题意:有n个盒子，然后每个盒子有f[i]个，你需要拿出来s个球，问你一共有多少种选择。 解法：2^ n的状态，枚举说那些花坛的花取超过了，剩下的用C(n−1，sum+n−1)隔板法计算个数，注意奇数的位置要用减的，偶数的位置用加的，容斥原理。
//CF 451E #include <bits/stdc++.h> using namespace std; const long long mod = 1e9+7; long long qmod(long long a, long long n) { long long res = 1; while(n){ if(n&1) res = res*a%mod; a = a*a%mod; n >>= 1; } return res; } long long C(long long a, long long b) { if(a < b) return 0; if(b > a - b) b = a - b; long long up = 1, down = 1; for(long long i = 0; i < b; i++){ up = up*(a-i)%mod; down = down*(i+1)%mod; } return up*qmod(down, mod-2)%mod; } long long lucas(long long a, long long b){ if(b == 0) return 1; return C(a%mod, b%mod)*lucas(a/mod, b/mod)%mod; } long long s, f[25]; int n; long long gao() { long long ans = 0; for(int i = 0; i < (1<<n); i++){ long long sgn = 1, sum = s; for(int j = 0; j < n; j++){ if(i&(1<<j)){ sum -= f[j]+1; sgn*=-1; } } if(sum < 0) continue; ans += sgn*lucas(sum+n-1, n-1)%mod; ans%=mod; } return (ans+mod)%mod; } int main() { scanf("%d%lld", &n, &s); for(int i = 0; i < n; i++) scanf("%lld", &f[i]); printf("%lld\n", gao()); return 0; }