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 long

using namespace std;

LL qmod(LL a,LL b)

{

    LL res=;

    if(a>=MOD)a%=MOD;

    while(b)

    {

        if(b&)res=res*a%MOD;

        a=a*a%MOD;

        b>>=;

    }

    return res;

}

LL inv(LL a)

{

    return qmod(a,MOD-);

}

LL invmod[];

LL C(LL n,LL m)

{

    if(n<m)return ;

    LL ans=;

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

        ans=(n-i+)%MOD*ans%MOD*invmod[i]%MOD;

    return ans;

}

LL f[],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-,n-);

        ans%=MOD;

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

        return ;

    }

    gao(now+,sum,flag);

    gao(now+,sum+f[now]+,-flag);

}

int main() {

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

        invmod[i]=qmod(i,MOD-);

    cin>>n>>s;

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

        cin>>f[i];

    ans=;

    gao(,,);

    cout<<(ans%MOD+MOD)%MOD<<endl;

    return ;

}