这题又是容斥原理，最近各种做容斥原理啊。当然，好像题解给的不是容斥原理的方法，而是用到Lucas定理好像。这里只讲容斥的做法。
题意：从n个容器中总共取s朵花出来，问有多少种情况。其中告诉你每个盒子中有多少朵花。
分析：其实就是求方程: x1+x2+...+xn = s 的整数解的个数，方程满足： 0<=x1<=a[1], 0<=x2<=a[2]...
设：A1 = {x1 >= a[1]+1} , A2 = {x2 >= a[2]+1} , .... , An = {xn >= a[n]+1}. 全集S = (n+s-1,s)
所以容斥原理可求得答案。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define Mod 1000000007 #define lll __int64 #define ll long long using namespace std; #define N 100007 ll a[22]; ll inv[30]; ll fastm(ll a,ll b) { ll res = 1LL; while(b) { if(b&1LL) res = (res*a)%Mod; b >>= 1; a = (a*a)%Mod; } return res; } ll comb(ll n,ll r) { if(r > n) return 0; r = min(r,n-r); n%=Mod; ll ans = 1LL; for(int i=0;i<=r-1;i++) { ans = ans*(n-i)%Mod; ans = ans*inv[i+1]%Mod; } return ans; } int calc(int s) { int cnt = 0; while(s) { if(s&1) cnt++; s >>= 1; } return cnt; } int main() { int n,i; ll s; for(i=1;i<=30;i++) inv[i] = fastm(i,Mod-2); while(cin>>n>>s) { for(i=0;i<n;i++) cin>>a[i]; ll ans = 0; int S = (1<<n)-1; for(int state=0;state<=S;state++) { ll r = s; int tmp = state; int cnt = calc(state); i=0; while(i<n) { if(tmp&1) r -= (a[i]+1); tmp >>= 1; i++; } if(r < 0) continue; ll cb = comb(n+r-1,r); if(cnt%2) cb = -cb; ans = (ans+cb+Mod)%Mod; } printf("%I64d\n",ans); } return 0; }