CodeForces - 451E Devu and Flowers (容斥+卢卡斯)

题意：有N个盒子，每个盒子里有fi 朵花，求从这N个盒子中取s朵花的方案数。两种方法不同当且仅当两种方案里至少有一个盒子取出的花的数目不同。

分析：对有k个盒子取出的数目超过了其中的花朵数，那么此时的方案数根据放球模型是C(N+t-1,N-1)，其中t是s-(k个盒子超过其数目的最小数量)。显然t<0该方案不存在。

而k个盒子超过其数目的最小数量是对应盒子数+1的和。

因为t的值可能很大,所以需要用Lucas定理计算组合数。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5+;

const int mod = 1e9+;

LL Pow(LL x, LL n, LL p)

{

    LL res=;

    while(n)

    {

        if(n&) res=x*res%p;

        x=x*x%p;

        n>>=;

    }

    return res;

}

LL Lucas(LL n, LL k, LL p)

{

    if(k>n-k) k=n-k;

    LL res=;

    while(n&&k){

        LL n0=n%p, k0=k%p;

        LL a=,b=;

        for(LL i=n0; i>n0-k0; i--) a=a*i%p;

        for(LL i=; i<=k0; i++) b=b*i%p;

        res = res*a*Pow(b, p-, p)%p;

        n/=p; k/=p;

    }

    return res;

}

LL f[];

int main()

{

    #ifndef ONLINE_JUDGE

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

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

    #endif

    LL n,s;

    while(scanf("%lld %lld",&n,&s)==){

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

            scanf("%lld", &f[i]);

        }

        LL up = 1LL << n;

        LL ans = Lucas(n+s-,n-,mod);

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

            int bit = ;

            LL t= s;

            for(int j=;j<n;++j){

                if(i &(<<j)){

                    bit++;

                    t -= f[j] + ;

                }

            }

            if(t<) continue;

            if(bit & ) ans = (ans+mod -Lucas(n+t-,n-,mod))%mod;

            else ans = (ans+Lucas(n+t-,n-,mod))%mod;

        }

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

    }

    return ;

}

巴特西

CodeForces - 451E Devu and Flowers (容斥+卢卡斯)

最新文章

热门文章