CF451E Devu and Flowers (组合数学+容斥)

题目大意：给你$n$个箱子，每个箱子里有$a_{i}$个花，你最多取$s$个花，求所有取花的方案，$n<=20$,$s<=1e14$,$a_{i}<=1e12$

容斥入门题目

把取花想象成往箱子里放花，不能超过箱子上限

$n$很小，考虑状压

如果去掉$a_{i}$的限制，我们取物品的方案数是$C_{s+n-1}^{n-1}$，可以想象成$s+n-1$个小球，我们取出$n-1$个隔板，分隔出来的其他$n$个部分就是每个箱子里花的数量

但这样会算入不合法的方案，我们需要再去掉不合法的方案

假设我们要满足i合法，那么首先分配给$i$，$ai+1$朵花，来保证它是不合法的

然后，剩余$s+n-(ai+1)-1$朵花，我们仍然要分配给$n$个箱子，取出$n-1$个隔板，总方案数减去$C_{s+n-(ai+1)-1}^{n-1}$

然而我们由算入了一些情况，即$i$不合法，$j$也不合法$(j!=i)$，在计算$i$和计算$j$时都去掉了这种情况，我们还要把它加回来

总方案再加回来$C_{s+n-(ai+aj+2)-1}^{n-1}$

然后又多减掉了$i,j,k$都不合法....依次容斥即可

公式太长，也不好理解就不列了

这道题的组合数很大，不能直接求，我们需要一些优化

因为$n$很小，但$s$很大，所以上下化简掉阶乘里那一段特别长的部分，剩下的$O(n)$暴力计算就行了

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 150

 #define uint unsigned int

 #define ll long long

 #define ull unsigned long long

 #define mod 1000000007

 using namespace std;

 //re

 /*int gint()

 {

     int ret=0,fh=1;char c=getchar();

     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}

     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}

     return ret*fh;

 }*/

 int n;

 ll sum,ma;

 ll a[N],mu[N],inv[N],minv[N];

 ll qpow(ll x,ll y){

     ll ans=;

     if(y){

         if(y&) ans=ans*x%mod;

         x=x*x%mod,y>>=;

     }return ans;

 }

 void Pre(){

     minv[]=minv[]=inv[]=inv[]=;

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

         inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,minv[i]=minv[i-]*inv[i]%mod;

 }

 ll C(ll a,ll b)

 {

     ll ans=;

     if(b>a) return ;

     if(b==) return ;

     for(ll j=a-b+;j<=a;j++)

         ans=j%mod*ans%mod;

     ans=ans*minv[b]%mod;

     return ans;

 }

 ll Lucas(ll a,ll b)

 {

     if(b>a) return ;

     if(a<mod&&b<mod) return C(a,b);

     else return Lucas(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;

 }

 int main()

 {

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

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

     int tot=(<<n)-;

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

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

     ll ans=;

     Pre();

     for(int s=;s<=tot;s++)

     {

         ll res=ma;int cnt=;

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

             if(s&(<<i)) res-=a[i]+,cnt++;

         if(res<) continue;

         (ans+=1ll*(cnt&?-:)*Lucas(res+n-,n-)%mod+mod)%=mod;

     }

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

     return ;

 }

巴特西

CF451E Devu and Flowers (组合数学+容斥)

最新文章

热门文章