codeforces 415E E. Devu and Flowers(组合数学+容斥原理)

时间:2022-12-19 00:08:21

题目链接:

codeforces 415E


题目大意:

给出n个盒子,每个盒子有 fi 朵花,每个盒子的花颜色相同,不同盒子的花颜色不同,问有多少种方案能恰巧选出s朵花。


题目分析:

  • 直接做感觉比较复杂,所以想容斥的做法。
  • 如果不考虑每个盒子取的花有个数限制,那么结果是 (n1+s,n1) ,通过插板法获得的方案数。
  • 然后我们考虑对于每个盒子选取大于x个的方案数就是 (n1x1+s,n1)
  • 然后直接容斥做就可以了。

AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;
LL s,f[25],inv[25];
const LL mod = 1e9+7;

LL Inv ( LL num , LL x )
{
LL ret = 1;
while ( x )
{
if ( x&1 )
{
ret *= num;
ret %= mod;
}
num *= num;
num %= mod;
x >>= 1;
}
return ret;
}

void init ( )
{
for ( int i = 1 ; i < 21 ; i++ )
inv[i] = Inv( i , mod-2 );
}

LL com ( LL n , LL m )
{
if ( n < m ) return 0LL;
if ( n== m ) return 1LL;
LL ret = 1;
for ( LL i = n; i >= (n-m+1) ; i-- )
{
ret *= inv[n+1-i];
ret %= mod;
ret *= i%mod;
ret %= mod;
}
return ret;
}

int main ( )
{
init ( );
while (~scanf ( "%d%lld" , &n , &s ) )
{
for ( int i = 0 ; i < n ; i++ )
scanf ( "%lld" , &f[i] );
int total = 1<<n;
LL ans = com ( s+n-1 , n-1 );
for ( int i = 1 ; i < total ; i++ )
{
int cnt = 0;
LL x = 0;
for ( int j = 0 ; j < n ; j++ )
if ( (1<<j)&i )
{
x += f[j]+1LL;
cnt++;
}
if ( cnt&1 )
{
ans -= com ( s+n-1-x , n-1 );
ans = (ans%mod+mod)%mod;
}
else
{
ans += com ( s+n-1-x , n-1 );
ans %= mod;
}
}
printf ( "%lld\n" , ans );
}
}