题目：
题意：有n个盒子（n<=20）,每个盒子中有10^12个小球，现从每个盒子中取出若干球（可为0），求共取出s个小球（s<=10^14）的方案数。
组合数学问题，求C(n,m).但n,m过大时，可用卢卡斯定理.
卢卡斯定理：C(n,m) %p = C(n/p,m/p) * C(n%p,m%p)
从n个盒子中取出s个球的方案数，相当于插板，即 C(s+n-1,n-1).注意这是没有限制条件的情况。
还要考虑哪些盒子取超了。
违法情况和 = 1个盒子取超的情况数 – 2个的 + 3个的 ….(容斥定理)
然后拿总方案数减去违法的，就是最终结果。总方案数 = C(s+n-1,n-1)
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<set>#include<cmath>using namespace std;typedef long long ll;const int N = 1e5+10;const ll mod = 1e9+7;const ll MOD = 1e9+7;ll k_pow(ll a,ll n,ll p){ll ans = 1ll, mo = a;while(n){if(n&1) ans = (ans * mo)%p;mo = (mo * mo)%p;n /= 2;}return ans;}ll cal(ll n,ll m,ll p){if(m>n) return 0;ll ans = 1ll;ll wt = 1ll;if(m>n-m) m = n-m;for(int i=1;i<=m;i++){ans = (ans * (n-i+1))%p;wt = (wt * i)%p;}wt = k_pow(wt,p-2,p);ans = (ans * wt)%p;return ans;}ll lucas(ll n,ll m,ll p){if(m==0) return 1;return ( lucas(n/p,m/p,p) * cal(n%p,m%p,MOD) )%p;}int n;ll s,f[30];int main(){while(scanf("%d%I64d",&n,&s)!=EOF){ll sum = 0;for(int i=0;i<n;i++){scanf("%I64d",&f[i]);sum += f[i];}ll ans = 0;for(int st=0;st<(1<<n);st++){int fl = 1;ll ts = s;for(int i=0;i<n;i++) if((1<<i)&st){fl *= -1;ts -= f[i]+1;}if(ts<0) continue;ans = (ans + fl*lucas(ts+n-1,n-1,MOD))%MOD;}ans = (ans + MOD)%MOD;cout<<ans<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，也有伤心的，既有令人兴奋的，也有令人灰心的，
