CF451E Devu and Flowers(容斥)

题目大意

\(n\)种花每种\(f_i\)个，求选出\(s\)朵花的方案。不一定每种花都要选到。

\(n\le 20\)

解法

利用可重组合的公式。

不考虑\(f_i\)的限制，直接可重组合的方案是，意思是从可以重复的\(n\)个元素中取出\(r\)个的个数。注意，根据定义，此时\(r\)种每个都要选。

考虑限制怎么办，我们先容斥。

我们可以钦定某些花选择了\(f_i+1\)次，代表这个花选出不合法的了。

那么为什么不是钦定\(f_i+0,2 \dots233666\dots \infin\) 呢？

是因为，我们钦定这种花选择了\(f_i+1\)后，就保证这种花超过限制了。

此时可重组合的公式仍然可以选择\(i\)号花，所以考虑到了\(i\)号花选择了\(\ge f_i+1\)的情况。

所以我们钦定\(f_i+1\)朵花就好了。

根据容斥原理，所有花不超过限制的方案数为

//@winlere

#include<bits/stdc++.h>

#define int long long

using namespace std;  typedef long long ll;

template < class ccf > inline ccf qr(ccf ret){      ret=0;

      register char c=getchar();

      while(not isdigit(c)) c=getchar();

      while(isdigit(c)) ret=ret*10+c-48,c=getchar();

      return ret;

}inline int qr(){return qr(1);}

const int maxn=25;

const ll mod=1e9+7;

inline ll Pow(ll base,ll p){

      base%=mod;

      register ll ret=1;

      for(;p;p>>=1,base=base*base%mod)

	    if(p&1) ret=ret*base%mod;

      return ret;

}

ll data[maxn],s,ans,inv[maxn]={1},jie[maxn]={1};

int n;

inline ll C(const ll&n,const ll&m){

      if(n<m||m<0||n<0)return 0;

      if(n==m)return 1;

      register ll ret=inv[m];

      for(register ll t=n;t>=n-m+1ll;--t)

	    ret=t%mod*ret%mod;

      return ret;

}

#undef int

int main(){

#define int long long

#ifndef ONLINE_JUDGE

      freopen("in.in","r",stdin);

      //freopen("out.out","w",stdout);

#endif

      for(register int t=1;t<maxn;++t)

	    inv[t]=inv[t-1]*Pow(t,mod-2ll)%mod;

      n=qr();s=qr(1ll);ans=C(s+n-1ll,n-1ll);

      for(register int t=1;t<=n;++t)

	    data[t]=qr(1ll);

      for(register int t=1,edd=1<<n,cnt=0;t<edd;++t){

	    ll f=cnt=0,delt;

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

		  if(t<<1>>i&1)

			f+=data[i]+1ll,++cnt;

	    delt=C(s-f+n-1ll,n-1ll);

	    if(cnt&1) ans=(ans-delt)%mod,ans=ans<0?ans+mod:ans;

	    else ans=(ans+delt)%mod;

      }

      cout<<ans<<endl;

      return 0;

}