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

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的小块，组成一个面积 …

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)个家族组 …

指数型母函数网上的资料不是很多，推荐毛杰明的09年国家集训队论文《母函数的性质及应用》 以及Richard A.Brualdi 所著的《组合数学》的第七章来看...倒不用全看懂..但是这本上面干货比较多。 我来说下自己的理解： 指数型母函数和普通型母函数（不加普通二字也是指它）的区别是后者是用来求解组合问题（顺序无关行），而前者是求解排列问题（不同的顺序属于不同的方案）。 对于多重排列问题，由于某种元素可能有多个，需要去掉它的重复度（除以该种元素的个数的阶乘），而这个除以阶乘的形式和泰勒级数展开中的一些函数的展开形式一致（或者是一些变形）。 因此母函数可以用泰勒级数来化简。 这是求解这类问题最核心的内容。 也有直接算的。比如这 …

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 + …

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比较大，滚动一下应该可以... 然后看到别人的题解里写到 …

http://poj.org/problem?id=3734 题意+思路同******hdu2065红色病毒解题报告 /* *********************************************** Author :111qqz Created Time :2016年02月27日 星期六 16时39分53秒 File Name :code/poj/3734.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

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!+... …

http://acm.hdu.edu.cn/showproblem.php?pid=1521 题意：有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB","BA"两种。 思路：指数型母函数。 对于相同的元素，需要去掉该元素的重复度，即为元素个数的阶乘。具体做法是用double类型存储（方案数除以重复度），然后在最后把阶乘乘回来四舍五入取整（为什么是四舍五入？） /* *********************************************** Author :111qqz Created …

从这里母函数（Generating function）详解学习了普通型母函数 #include <iostream> using namespace std; // Author: Tanky Woo // www.wutianqi.com const int _max = 10001; // c1是保存各项质量砝码可以组合的数目 // c2是中间量，保存没一次的情况 int c1[_max], c2[_max]; int main() { //int n,i,j,k; int nNum; // int i, j, k; while(cin >> nNum) { for(i=0; i<=nNum; …