CodeForces451E Devu and Flowers

题目链接

问题分析

没有想到母函数的做法……

其实直接看题思路挺简单的。发现如果每种花都有无限多的话，问题变得十分简单，答案就是\(s+n-1\choose n - 1\)。然后发现\(n\)只有\(20\)，于是大力容斥一波就完事了。

参考代码

#include <cstdio>const long long Max_n = 30;
const long long Mod = 1000000007;
long long n, s, f[ Max_n ];void Exgcd( long long a, long long b, long long & x, long long & y ) {if( b == 0LL ) { x = 1LL; y = 0LL; return; }Exgcd( b, a % b, y, x );y -= a / b * x;return;
}long long Inv( long long a ) {long long x, y;Exgcd( a, Mod, x, y );if( x < 0 ) x += Mod;return x;
}long long C( long long n, long long m ) {long long Ans = 1;for( long long i = 1; i <= m; ++i ) Ans = Ans * ( ( n - i + 1 ) % Mod ) % Mod;for( long long i = 1; i <= m; ++i ) Ans = Ans * Inv( i ) % Mod;return Ans;
}int main() {scanf( "%lld%lld", &n, &s );for( long long i = 1; i <= n; ++i ) scanf( "%lld", &f[ i ] );long long Ans = 0;for( long long i = 0; i < 1 << n; ++i ) {long long t, Cnt = 0, Pos = s;for( t = i; t; t >>= 1 ) if( t & 1 ) ++Cnt;for( long long j = 1, t = i; t; t >>= 1, ++j ) if( t & 1 ) Pos -= f[ j ] + 1;if( Pos < 0 ) continue;Ans += ( Cnt & 1 ) ? -C( Pos + n - 1, n - 1 ) : C( Pos + n - 1, n - 1 );Ans = ( Ans + Mod ) % Mod;}printf( "%lld\n", Ans );return 0;
}