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

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 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).

嗯。。。

我推到了这步:(1 - x(f1 + 1)) * .. * (1 - x(fn + 1)) * (1 - x)( - n).

然后不知所措了。

一个不会的点是,一般意义的二项式定理不会,也就是指数为负数的。

然后后面那一串,由于n才20.所以直接暴力展开多项式我是能想到的。。。但是依然不知道怎么写。还有递归的求解方法。。。没有特别明白。

此外需要lucas定理求大组合数,以及预处理一个逆元(代码中的ny数组存的不仅仅是逆元)

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz