首页 > 代码库 > codeforces 451E Devu and Flowers

codeforces 451E Devu and Flowers

2024-07-16 10:21:04   219人阅读

题意：有n个瓶子每个瓶子有 f【i】 支相同的颜色的花（不同瓶子颜色不同，相同瓶子花视为相同） 问要取出s支花有多少种不同方案。

思路： 如果每个瓶子的花有无穷多。那么这个问题可以转化为  s支花分到n个瓶子有多少种方案  用隔板法就能解决 C(s+n-1,n-1) 。有限制之后我们可以 用 没限制的去减掉那些违反限制的 如果只有一个瓶子取得花超出上限 那么减去，两个瓶子 要加上（容斥原理） n只有20  就能暴力枚举那些取超过上限f【i】的瓶子并且在这些瓶子至少选出 f【i】+1 支花  统计即可。

#include <iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define MOD 1000000007#define LL long longusing namespace std;LL qmod(LL a,LL b){    LL res=1;    if(a>=MOD)a%=MOD;    while(b)    {        if(b&1)res=res*a%MOD;        a=a*a%MOD;        b>>=1;    }    return res;}LL inv(LL a){    return qmod(a,MOD-2);}LL invmod[50];LL C(LL n,LL m){    if(n<m)return 0;    LL ans=1;    for(int i=1;i<=m;++i)        ans=(n-i+1)%MOD*ans%MOD*invmod[i]%MOD;    return ans;}LL f[30],n,s;LL ans;void gao(int now,LL sum,int flag){    if(sum>s)return ;    if(now==n)    {        ans+=flag*C(s-sum+n-1,n-1);        ans%=MOD;    //    printf("%I64d\n",ans);        return ;    }    gao(now+1,sum,flag);    gao(now+1,sum+f[now]+1,-flag);}int main() {    for(int i=1;i<=20;++i)        invmod[i]=qmod(i,MOD-2);    cin>>n>>s;    for(int i=0;i<n;++i)        cin>>f[i];    ans=0;    gao(0,0,1);    cout<<(ans%MOD+MOD)%MOD<<endl;    return 0;}

 


联系
我们