BZOJ 1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店 (母函数,高精度)

1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 353  Solved: 190
[Submit][Status][Discuss]

Description

Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are: 1 @ US$3 + 1 @ US$2 1 @ US$3 + 2 @ US$1 1 @ US$2 + 3 @ US$1 2 @ US$2 + 1 @ US$1 5 @ US$1 Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

    约翰到奶牛商场里买工具.商场里有K(1≤K≤100).种工具,价格分别为1,2,…,K美元.约翰手里有N(1≤N≤1000)美元,必须花完.那他有多少种购买的组合呢?

Input

A single line with two space-separated integers: N and K.

    仅一行,输入N,K.

Output

A single line with a single integer that is the number of unique ways FJ can spend his money.

    不同的购买组合数.

Sample Input

5 3

Sample Output

5
思路:母函数裸题,还卡个高精度。。差评。。。

BZOJ 1643: [Usaco2007 Oct]Bessie’s Secret Pasture 贝茜的秘密草坪(母函数)

1643: [Usaco2007 Oct]Bessie’s Secret Pasture 贝茜的秘密草坪

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 330  Solved: 278
[Submit][Status][Discuss]

Description

农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮,草皮的边长总是整数(有时农夫约翰割草皮的刀法不合适,甚至切出了边长为0的正方形草皮),他已经把草皮放在了一个奶牛贝茜已经知道的地方。 贝茜总是希望把美味的草皮放到她的秘密庄园里,她决定从这些草皮中取出恰好4块搬到她的秘密庄园中,然后把它们分成1×1的小块,组成一个面积为N(1<=N<=10,000)个单位面积的部分。 贝茜对选出这样四块草皮的方法数很感兴趣,如果她得到了一个4个单位面积的部分,那么她可以有5中不同的方法选4块草皮:(1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,0,2).顺序是有效的:(4,3,2,1)和(1,2,3,4)是不同的方法。

Input

第一行:一个单独的整数N。

Output

单独的一行包含一个整数,表示贝茜选四块草皮的方案数。

Sample Input

4

Sample Output

5
思路:母函数。把四个位置看作四个式子。每个式子的i可以取从0到i*i<=n的最大值。

BZOJ 1630/2023: [Usaco2005 Nov]Ant Counting 数蚂蚁 (母函数)

 

2023: [Usaco2005 Nov]Ant Counting 数蚂蚁

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 149  Solved: 85
[Submit][Status][Discuss]

Description

    有一天,贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物.很快贝茜发现有些蚂蚁长得几乎一模一样,于是她认为那些蚂蚁是兄弟,也就是说它们是同一个家族里的成员.她也发现整个蚂蚁群里有时只有一只出来觅食,有时是几只,有时干脆整个蚁群一起出来.这样一来,蚂蚁们出行觅食时的组队方案就有很多种.作为一头有数学头脑的奶牛,贝茜注意到整个蚂蚁群由T(1≤T≤1000)个家族组成,她将这些家族按1到T依次编号.编号为i的家族里有Ni(1≤Ni≤100)只蚂蚁.同一个家族里的蚂蚁可以认为是完全相同的.
    如果一共有S,S+1….,B(1≤S≤B≤A)只蚂蚁一起出去觅食,它们一共能组成多少种不同的队伍呢?注意:只要两支队伍中所包含某个家族的蚂蚁数不同,我们就认为这两支队伍不同.由于贝茜无法分辨出同一家族的蚂蚁,所以当两支队伍中所包含的所有家族的蚂蚁数都相同时,即使有某个家族换了几只蚂蚁出来,贝茜也会因为看不出不同而把它们认为是同一支队伍.    比如说,有个由3个家族组成的蚂蚁群里一共有5只蚂蚁,它们所属的家族分别为1,1,2,2,3.于是出去觅食时它们有以下几种组队方案:
  ·1只蚂蚁出去有三种组合:(1)(2)(3)
  ·2只蚂蚁出去有五种组合:(1,1)(1,2)(1,3)(2,2)(2,3)
  ·3只蚂蚁出去有五种组合:(1,1,2)(1,1,3)(1,2,2)(1,2,3)(2,2,3)
  ·4只蚂蚁出去有三种组合:(1,2,2,3)(1,1,2,2)(1,1,2,3)
  ·5只蚂蚁出去有一种组合:(1,1,2,2,3)
    你的任务就是根据给出的数据,计算蚂蚁们组队方案的总数.

Input

    第1行:4个用空格隔开的整数T,A,S,B.
    第2到A+1行:每行是一个正整数,为某只蚂蚁所在的家族的编号.

Output

    输出一个整数,表示当S到B(包括S和B)只蚂蚁出去觅食时,不同的组队方案数.
    注意:组合是无序的,也就是说组合1,2和组合2,1是同一种组队方式.最后的答案可能很大,你只需要输出答案的最后6位数字.注意不要输出前导0以及多余的空格.

Sample Input

3 5 2 3
1
2
2
1
3
INPUT DETAILS:Three types of ants (1..3); 5 ants altogether. How many sets of size 2 or
size 3 can be made?

Sample Output

10

OUTPUT DETAILS:

5 sets of ants with two members; 5 more sets of ants with three members

题意:有n只蚂蚁,T个种族,输入给出第i只蚂蚁属于哪个种族(每个种族最多有100只蚂蚁)
设f[x]表示x只蚂蚁的组成的方案数(只要两支队伍中所包含某个家族的蚂蚁数不同,我们就认为这两支队伍不同) 现在要求 [S,B]区间中 f[x]的和 。
思路:时间主要花在的读题上。。。这两个题目一个没描述一个数据有问题。。。得一起看。
题目读懂以后觉得是母函数。。
先统计出每种种群的蚂蚁个数,然后就变成了

hdu2152解题报告  这道题的模型。。。

然后求母函数的时候直接求到B的,那么之前的也都求出来了。

最后累加。

由于答案保留最后六位数字,所以算的时候要%1E6…

1A,好开心。。。。

母函数的思维上难度很小,说白了都是套路。

感觉比那些dp+前缀和乱搞的做法高到不知哪里去了(反正对我这种dp废是这样的)

 

指数型母函数总结

指数型母函数网上的资料不是很多,推荐毛杰明的09年国家集训队论文《母函数的性质及应用》

以及Richard A.Brualdi 所著的《组合数学》的第七章来看…倒不用全看懂..但是这本上面干货比较多。

我来说下自己的理解:

指数型母函数和普通型母函数(不加普通二字也是指它)的区别是后者是用来求解组合问题(顺序无关行),而前者是求解排列问题(不同的顺序属于不同的方案)。

对于多重排列问题,由于某种元素可能有多个,需要去掉它的重复度(除以该种元素的个数的阶乘),而这个除以阶乘的形式和泰勒级数展开中的一些函数的展开形式一致(或者是一些变形)。

因此母函数可以用泰勒级数来化简。

这是求解这类问题最核心的内容。

 

也有直接算的。比如这个hdu1521排列组合hdu1521排列组合解题报告但是由于阶乘的存在。。这类问题求解的范围十分有限。
所以更多的是下面这些题,难度递增,建议先独立思考…
hdu2065解题报告
poj1322 chocolate解题报告
cf451E解题报告

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

 

 

 

 

poj 1322 chocolate (指数型母函数 )

http://poj.org/problem?id=1322
题意:

 

 

思路:别看n,m很大。。。但是想一下。。m显然不可能大于c(如果大于c,那么根据抽屉原理,至少存在一种巧克力大于一个,然而大于一个就会被取走…矛盾)   这样概率为0.m也不可能大于n,因为最好的情况就是取出的巧克力都放在了桌子上,如果总共取的还不到n个,又怎么可能剩下m(m>n)个呢。此外,还需要n,m奇偶性相同,否则设n-m=2K+1 ,说明如果要剩余m个,那么就要减少2k+1个,但是巧克力是两个两个减少的,减少的个数一定是偶数,因此矛盾。所以n,m奇偶性相同。

 

接下来可以用概率dp做,由于n比较大,滚动一下应该可以… 然后看到别人的题解里写到当n>1000的时候已经趋向平衡(达到了要求的精度)… 这道题dp写起来的确容易,也不是很难想。

不过作为dp废宁愿选择数学方法,指数型母函数。

 

分析可知,取过偶数次的巧克力消失,只有取过奇数次的巧克力会留在桌子上。

那么要剩余m个巧克力,也就是有m种巧克力取了奇数次,剩下的c-m种巧克力取了偶数次。

对应的的生成函数(母函数)分别是(e^x-e(-x))/2和(e^x+e(-x))/2  (推倒类似)hdu2065红色病毒解题报告

总事件个数为c^n

根据古典概型,所求概率为 (Gn*n!*C[c][m])/(c^n)  其中Gn*n!为生成函数,C[c][m]是因为不确定c种巧克力中的哪m种取了奇数个。

现在的问题就成了求Gn中x^n的系数。。我就是因为这个卡了两天这道题。。。

 

其实模拟就好,复杂度O(c^2)而已。。主要是好久没写二项式定理。。。有点忘了(手动智力-2)

 

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

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

题意+思路同hdu2065红色病毒解题报告

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

http://acm.hdu.edu.cn/showproblem.php?pid=2065
题意:a,b,c,d四种元素,a,c只能出现偶数次(包括0次),b,d没有限制,问n个(2^64)个元素有多少种不同的组合。
思路:指数型母函数。。。n大的没办法用之前的办法做。

先来看下我们要求的式子:A=(1+x/1!+x^2/2!+x^3/3!……)^2*(1+x^2/2!+x^4/4!+x^6/6!……)^2.

其实一共四个式子相乘,但是a和c的情况相同,b和d的式子相同。

我们要求的是x^n的系数。。。n太大了。。直接搞肯定不行。

想到微积分学的泰勒展开。

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

其实这里x的范围没有意义,因为母函数关注的是系数,不会代入x的值,所以可以不用考虑收敛性。

那么第一项(1+x/1!+x^2/2!+x^3/3!……)^2就可以换成(e^x)^2

第二项没有奇数项,很容易想到可以写成((e^x+e^(-x))/2)^2

继续化简:4*A=(e^x)^2*((e^x+e^(-x))/2)^2

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

我们要的是x^n的系数,再正向泰勒展开,得到x^n的系数应该是 (4^n+2*2^n)/4,也就是4^(n-1)+2^(n-1)

因为只要后两位的结果,其实就是结果%100.快速幂搞之。

以及,2^64 long long 存不下,应该用unsigned long long ,类型说明符是 %llu

 

 

 

 

hdu 1521 排列组合 (指数型母函数模板题)

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

题意:有n种物品,并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B,并且数量都是1,从中选2件物品,则排列有”AB”,”BA”两种。

思路:指数型母函数。
对于相同的元素,需要去掉该元素的重复度,即为元素个数的阶乘。具体做法是用double类型存储(方案数除以重复度),然后在最后把阶乘乘回来四舍五入取整(为什么是四舍五入?)

普通型母函数总结

从这里母函数(Generating function)详解学习了普通型母函数

① 、首先对c1初始化,由第一个表达式(1+x+x^2+..x^n)初始化,把质量从0到n的所有砝码都初始化为1.

② 、 i从2到n遍历,这里i就是指第i个表达式,上面给出的第二种母函数关系式里,每一个括号括起来的就是一个表达式。

③、j 从0到n遍历,这里j就是(前面i個表达式累乘的表达式)里第j个变量,(这里感谢一下seagg朋友给我指出的错误,大家可以看下留言处的讨论)。如(1+x)(1+x^2)(1+x^3),j先指示的是1和x的系数,i=2执行完之后变为

(1+x+x^2+x^3)(1+x^3),这时候j应该指示的是合并后的第一个括号的四个变量的系数。

④ 、 k表示的是第j个指数,所以k每次增i(因为第i个表达式的增量是i)。

⑤ 、把c2的值赋给c1,而把c2初始化为0,因为c2每次是从一个表达式中开始的。

讲得不错,之前第三点注释有问题没想到现在已经改过来了2333.

 

说说我的理解:母函数其实形式上就是函数…但是关注的是系数。。就像一排挂衣架一样。

普通型母函数的作用就是通过模拟多项式乘法的方式解决一类组合计数问题。

一般能由普通型母函数解决的问题也能由dp或者递推来解决,但是母函数可能更容易理解(对我个人来说

这类问题呢,一般有如下几种问法。

一种是对于每类物品的个数,可能每类个数有限,也可能无限。

如果无限个,那么就根据n的大小作为一个循环的上限,因为n+1以及以后的指数肯定对答案没有贡献。

比如这道题: hdu1028解题报告

如果每类都有限,那么就根据每类物品作为上限。这时j那一层循环要不断累加(变量cur)当前能得到的最大价值(也就是多项式的最大指数) 比如这道hdu1085解题报告
也可能不仅要求上限,还要求有下限,也就是要求每类物品的个数必须在一个范围内。比如这道hdu2152解题报告

也可能两种要同时考虑。比如这道hdu2082解题报告 不过如果就算把所有数量算上也不会太大(数组存不下)的话,不考虑也可以(我懒)

还有,每种元素并不一定像整数拆分一样是连续的,可能像硬币问题一样只有1分,2分,5分的硬币,或者只能是平方数hdu1398解题报告 只能是素数hdu2189解题报告

还有一点,不一定所有元素对答案都是正的贡献,也可能是负的贡献。 这类问题主要是和天平有关。给你若干砝码,问你能称量出多少的重量。由于砝码可以放左边也可以放右边,所以每个对答案有正负两种贡献(不放就是没贡献)
比如这道hdu1709解题报告和这道hdu5616解题报告

最后就是稍微难一点的一类问题:对单个元素的个数没有限制,但是对所有元素的总个数有限制。这类题我们需要增加一维。现在用a[i][j]表示由j个元素组成价值为i的方案数。具体见这里:hdu2069解题报告

 

20160303 update: 还有一种当个数特别多。。以至于不可能通过循环来实现的情况。需要通过泰勒展开来化简。比较经常用的一个式子是 1+x+x^2+..+x^n=(1-x^(n+1))(1-x)

比如这道题:
codeforces451EDevu and Flowers解题报告

hdu 1284 铅笔兑换问题(母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=1284
题意:有1分,2分,3分的钱若干,问组成n(n<=32767)分钱的方案数。
思路:母函数.

需要注意的是多组数据。每次都搞会TLE,可以先预处理出来存到数组里,每次直接调用。如果预处理时间也还是慢的话,可以先跑出来,然后打表。这算一个小tip吧2333

 

hdu 2082 找单词 (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=2082
题意:26个字母,第i个字母有x[i]个,价值为i.问能组成多少个价值不超过50的单词(注意这里的单词只考虑字母的组成,不考虑字母之间的顺序)
思路:母函数。

BC #70 B || hdu 5616 Jam’s balance (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=5616
题意:有n个(n<=20)砝码,第i个重量为w[i],给出m个查询,每个查询一个重量,问这个重量能否被称量出。 思路:暴力(没美感),01背包(不会),母函数(瞬间成了傻逼题)和这题很像 hdu1709 balance
hdu1709解题报告

hdu 2152 Fruit (母函数)

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

题意:中文题目,大概是说有n(<=100)种水果,第i种至少拿l[i]个,最多拿r[i]个,现在挑选m种水果组成一个果盘,问方案数。

思路:母函数,之前的题目都是只对上界有限制,其实对下界有限制是一样的。以及。。。一开始以为是拿100元买。。。后来发现是“一打百元大钞”23333  其实再出难点可以对个数以及钱数都有限制。。。。

 

 

hdu 2069 Coin Change(母函数)

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

题意:有1,5,10,25,50面值的硬币若干,问组成n元钱有多少种不同的方案。一个额外的要求是硬币的总是不能超过100.(那句 your program should be able to handle up to 100 coins.真的是这个意思。。。?感觉好坑。。。)

思路:还是母函数,但是由于有了多硬币总数的限制条件,需要加一维.a[i][j]表示j个硬币组成i元钱的方案数(越来越想dp了) 如果转移的时候需要需要加一层硬币的个数。具体见代码。