Posts

http://codeforces.com/problemset/problem/451/E 题意;有n个花坛，要选s支花，每个花坛有f[i]支花，同一个花坛的花颜色相同，不同花坛的花颜色不同，问说可以有多少种组合。 思路：典型的母函数…然而s有点大，根据泰勒展开什么的…先转一下官方题解。

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奇偶性相同。

http://poj.org/problem?id=2356 题意：有 n 个数，从中选取若干个（1..n），和能被 n 整除。问是否有解，无解输出 0，有解的话，输出个数以及选择的 a[i]（不是 i）。

http://acm.hdu.edu.cn/showproblem.php?pid=1205 题意：有n种糖果，第i种糖果有a[i]个，相邻两次不能吃一样的糖果，问能否有办法吃完所有糖果… 思路：如果第i种糖果有k个的话，那么其他所有种类的糖果之和至少有k-1个，才可能吃完。复杂度O(n) 看到有人说是抽屉原理…..大概。。。？不过不太明显。。直接想就好吧

hdu1796 题意：给出n（<=2^31）以及m(<=10)个元素组成的无重复元素集合，集合元素0<=a[i]<=20,问有多少个小于n的数能至少被集合中的一个元素整除。

http://acm.hdu.edu.cn/showproblem.php?pid=4336 题意：有n种卡片，买一包干脆面得到第i种卡片的概率是p[i],每包干脆面最多有一张卡片，问收集齐所有卡片要买的干脆面的包数的数学期望。

http://poj.org/problem?id=3734 题意+思路同******hdu2065红色病毒解题报告

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

http://www.lydsy.com/JudgeOnline/problem.php?id=1610 题意：给出n个点，问有多少条直线，这些之间之间都不平行。 思路：求斜率（注意考虑斜率不存在），看有多少种斜率。 妈蛋。。。。斜率不存在是横坐标相等啊，不是纵坐标啊。。。蠢哭了好么。。。。。。

http://www.lydsy.com/JudgeOnline/problem.php?id=1607 题意：n个数，求对于每个数来说，其他n-1个数中是它约数的数的个数。

http://acm.hdu.edu.cn/showproblem.php?pid=1521 题意：有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB",“BA"两种。

从这里母函数（Generating function）详解学习了普通型母函数 1#include <iostream> 2using namespace std; 3// Author: Tanky Woo 4// www.wutianqi.com 5const int _max = 10001; 6// c1是保存各项质量砝码可以组合的数目 7// c2是中间量，保存没一次的情况 8int c1[_max], c2[_max]; 9int main() 10{ //int n,i,j,k; 11 int nNum; // 12 int i, j, k; 13 14 while(cin >> nNum) 15 { 16 for(i=0; i<=nNum; ++i) // ---- ① 17 { 18 c1[i] = 1; 19 c2[i] = 0; 20 } 21 for(i=2; i<=nNum; ++i) // ----- ② 22 { 23 24 for(j=0; j<=nNum; ++j) // ----- ③ 25 for(k=0; k+j<=nNum; k+=i) // ---- ④ 26 { 27 c2[j+k] += c1[j]; 28 } 29 for(j=0; j<=nNum; ++j) // ---- ⑤ 30 { 31 c1[j] = c2[j]; 32 c2[j] = 0; 33 } 34 } 35 cout << c1[nNum] << endl; 36 } 37 return 0; 38} ① 、首先对c1初始化，由第一个表达式(1+x+x^2+..x^n)初始化，把质量从0到n的所有砝码都初始化为1.

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

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

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

http://acm.hdu.edu.cn/showproblem.php?pid=2152 题意：中文题目，大概是说有n（<=100）种水果，第i种至少拿l[i]个，最多拿r[i]个，现在挑选m种水果组成一个果盘，问方案数。

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.真的是这个意思。。。？感觉好坑。。。）

http://acm.hdu.edu.cn/showproblem.php?pid=1709 题意：有n个砝码，第i个的重量为w[i]，问从1到sum(所有砝码的重量之和)那些重量无法称量。（所有质量都是整数） 思路：母函数。 一个砝码可以看做有三种状态，放，放左边（+），放右边（-）

http://acm.hdu.edu.cn/showproblem.php?pid=2189 题意：n个人可以分成若干组，每组人数都为素数，问有多少种分法。 思路：母函数。先预处理素数，记得多处理一点…

http://acm.hdu.edu.cn/showproblem.php?pid=1085 题意;一元的钱有num_1张，2元的钱有num_2张，5元的钱有num_5张，问最小的不能组成的钱是多少。 思路：有限个个数的母函数，并且不知道最好要多少，所以限制条件变成了不同种类钱的个数。统计0到num_1+2num_2+5num_5的方案数，第一个为0的就是答案。