首页 > 代码库 > codeforces 451E Devu and Flowers
codeforces 451E Devu and Flowers
题意:有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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。