Codeforces 451 E. Devu and Flowers（组合数学，数论，容斥原理）

传送门

解题思路：

假如只有 s 束花束并且不考虑 f ，那么根据隔板法的可重复的情况时，这里的答案就是

假如说只有一个 f 受到限制，其不合法时一定是取了超过 f 的花束

那么根据组合数，我们仍然可以算出其不合法的解共有：

最后，由于根据容斥，减两遍的东西要加回来，那么含有偶数个 f 的项为正，奇数个时为负。

答案就是：

搜索答案，使用Lucas定理，计算组合数上下约去。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 typedef long long lnt;

 const lnt mod=(lnt)(1e9+);

 int n;

 lnt s,ans;

 lnt f[];

 lnt ksm(lnt x,lnt y)

 {

     lnt ans=;

     while(y)

     {

         if(y&)

             ans=ans*x%mod;

         x=x*x%mod;

         y=y/;

     }

     return ans;

 }

 lnt Lucas(lnt n,lnt m)

 {

     if(n<mod&&m<mod)

     {

         if(n<m)    return ;

         if(n==m)return ;

         if(m==)return ;

         lnt nj=,mj=;

         lnt a=n-m,b=m;

         if(a>b)

             std::swap(a,b);

         lnt i=b+;

         while(i<=n)

         {

             nj=(nj*i)%mod;

             i++;

         }

         i=;

         while(i<=a)

         {

             mj=(mj*i)%mod;

             i++;

         }

         return ksm(mj,mod-)*nj%mod;

     }

     return Lucas(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;

 }

 lnt dle(lnt x)

 {

     return (((&x)^)<<)-;

 }

 void dfs(int p,int l,lnt sum)

 {

     if(p==n+)

     {

         ans=(ans+dle(l)*Lucas(s-sum+n-,n-))%mod;

         return ;

     }

     dfs(p+,l,sum);

     dfs(p+,l+,sum+f[p]+);

     return ;

 }

 int main()

 {

     scanf("%d%I64d",&n,&s);

     for(int i=;i<=n;i++)

         scanf("%I64d",&f[i]);

     ans=;

     dfs(,,);

     printf("%I64d\n",(ans%mod+mod)%mod);

     return ;

 }