# codeforces 451E Devu and Flowers (指数型母函数)

Posted by 111qqz on Wednesday, March 2, 2016

## TOC

http://codeforces.com/problemset/problem/451/E 题意;有n个花坛，要选s支花，每个花坛有f[i]支花，同一个花坛的花颜色相同，不同花坛的花颜色不同，问说可以有多少种组合。 思路：典型的母函数…然而s有点大，根据泰勒展开什么的…先转一下官方题解。

The number of ways to choose _N_ items out of _R_ groups where each item in a group is identical is equal to the number of integral solutions to _x_1 + _x_2 + _x_3..._x__R_ = _N_, where 0 ≤ _x__i_ ≤ _L__i_, where _L__i_ is the number of items in _i__th_ group. Number of integral solutions are coefficient of _x__N_ in [Product of (1 + _x_ + _x_ * _x_ + ..._x__L__i_) over all \$i\$].

You need to find coefficient of x__s in (1 + x + _x_2 + _x_3 +  + .._x__f_1) *  *  * (1 + x + _x_2 + _x_3 +  + ..x__f__n).

Using sum of Geometric progression we can say that(1 + x + _x_2 + _x_3 +  + .._x__f_1) = (1 - x(_f_1 + 1)) / (1 - x).

Substituting in the expression, we get (1 - x(_f_1 + 1)) / (1 - x) *  *  * (1 - x(f__n + 1)) / (1 - x).

= (1 - x(_f_1 + 1)) * .. * (1 - x(f__n + 1)) * (1 - x)( - n).

Now we can find x__s in (1 - x) - n easily. It is .

You can have a look at following link. to understand it better.

So now as s is large, we can not afford to iterate over s.

But n is small, we notice that (1 - x(f_1 + 1)) * .. * (1 - x(f__n + 1)) can have at most 2_n terms.

So we will simply find all those terms, they can be very easily computed by maintaining a vector<pair<int, int> > containing pairs of coefficients and their corresponding powers. You can write a recursive function for doing this.

How to find % p. As n + s - 1 is large and s is very small. You can use lucas’s theorem. If you understand lucas’s theorem, you can note that we simply have to compute .

Complexity: O(n * 2_n_).

``````/* ***********************************************
Author :111qqz
Created Time :2016年03月02日 星期三 20时54分07秒
File Name :code/cf/problem/451E.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL mod = 1E9+7;
int n;
LL s;
LL f[35];

int ny[35];
LL ksm(LL a,LL b)   //快速幂
{
LL res = 1;
while (b)
{
if (b&1) res = (res*a)%mod;
b>>=1;
a = (a*a)%mod;
}
return res;
}

void gny()  //ny数组存的不仅仅是逆元...
{
LL val=1  ;
for ( LL i = 1 ; i <= 20 ; i++) val = val*i%mod;
ny[20]=ksm(val,mod-2);
for ( LL i = 19 ; i+1 ; i--) ny[i]=(ny[i+1]*(i+1))%mod;
}

LL cal( LL x,LL y)   //lucas 定理求组合数
{
LL res  = 1LL;
for (LL  i = x ; i > x-y ;  i--)  res = (res*(i%mod))%mod;
res = (res*ny[y])%mod;
return res;
}
LL  solve(LL x,LL s)
{
if (s<0) return 0;
if (x==n+1) return cal(s+n-1,n-1);
return (solve(x+1,s)-solve(x+1,s-f[x]-1)+mod)%mod;
}
int main()
{
#ifndef  ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif

ios::sync_with_stdio(false);
gny();
cin>>n>>s;
for ( int i = 1 ; i <= n ; i++)
{
cin>>f[i];
}

LL ans = solve(1,s)%mod;

cout<<ans<<endl;

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````

「真诚赞赏，手留余香」