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

http://codeforces.com/problemset/problem/451/E

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 x1 + x2 + x3xR = N, where 0 ≤ xi ≤ Li, where Li is the number of items in ith group. Number of integral solutions are coefficient of xN in [Product of (1 + x + x * x + …xLi) over all \$i\$].

You need to find coefficient of xs in (1 + x + x2 + x3 +  + ..xf1) *  *  * (1 + x + x2 + x3 +  + ..xfn).

Using sum of Geometric progression we can say that(1 + x + x2 + x3 +  + ..xf1) = (1 - x(f1 + 1)) / (1 - x).

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

= (1 - x(f1 + 1)) * .. * (1 - x(fn + 1)) * (1 - x)( - n).

Now we can find xs 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(f1 + 1)) * .. * (1 - x(fn + 1)) can have at most 2n 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 * 2n).

## poj 3734 Blocks (指数型母函数，泰勒级数展开)

http://poj.org/problem?id=3734

## hdu 2065 “红色病毒”问题 (指数型母函数，泰勒级数展开)

http://acm.hdu.edu.cn/showproblem.php?pid=2065

e^x=1+x/1!+x^2/2!+x^3/3!+… (|x|<oo)

4*A = (e^(4x)+2*e^(2x)+1)