hdu 3929 Big Coefficients (递归形式的容斥原理+lucas定理的结论)

题意:F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am,求系数是奇数的项的个数。
思路:解题报告 涉及到的由lucas定理得到的推论的证明lucas定理证明 以及这篇理解里有递归形式的容斥定理的一般写法。。递归形式的容斥定理

第一次接触递归形式的容斥定理…还不是特别理解,据说要比循环的写法少一层msk(应该是少一个1<

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数组存的不仅仅是逆元)

 

 

 

 

codeforces 560 E. Gerald and Giant Chess (dp+lucas定理,求大组合数 mod p,p为质数)

dp方程想错了.果然还是欠练啊.

如果我们不考虑坏点,那么从 (0,0)到(x,y)的方案数是c(x+y,x)或者c(x+y,y)

因为有坏点的存在,我们可以逆向思维,先求出总数,然后减去那些由于坏点的影响不能走的方案数.

由于存在黑点i(x,y),从左上到该黑点的方案数sum[i] = C(x+y,x),其中如果在黑点i的左上还有黑点j(u,v),那么应该减去sum[j]*C(x-u+y-v)(y-u)

然后可以把坏点按照x为第一关键字,y为第二关键字排序.

从左上出发,往右下扫黑点.

还有一个考点是大组合数的求法

因为太大,递推也不行.

可以用欧拉公式求逆元的方法求解.

或者是lucas定理.

记得拿到骑士(1,1)到(n,m)的题和这道题很像.

也是从坐上到右下,中间有些坏点,不过骑士的走法并不是向下或者想有1步,而是向右p步,向下q步,或者向又q步,向下p步.

而且那道题的n和m是 10^9的数量级…

那道题的话就只能用lucas定理了貌似

这道题算是那道题的弱化版本,在此orz zhangk,果然厉害

所以我还是决定写lucas定理的解法

lucas定理适用于 求C(n,m)%p,p为素数 且n,m很大的情况.

引用一段题解: