http://www.lydsy.com/JudgeOnline/problem.php?id=1607 题意：n个数，求对于每个数来说，其他n-1个数中是它约数的数的个数。 思路：类似筛法，从小到大处理，数i对其所有倍数的数的答案有cnt[i]的贡献 。最后记得把自己是自己的约数的情况减掉。 /* *********************************************** Author :111qqz Created Time :2016年02月28日 星期日 01时06分35秒 File Name :code/bzoj/1607.cpp …

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

http://acm.hdu.edu.cn/showproblem.php?pid=1284 题意：有1分，2分，3分的钱若干，问组成n（n<=32767）分钱的方案数。 思路：母函数. 需要注意的是多组数据。每次都搞会TLE，可以先预处理出来存到数组里，每次直接调用。如果预处理时间也还是慢的话，可以先跑出来，然后打表。这算一个小tip吧2333 /* *********************************************** Author :111qqz Created Time :2016年02月27日 星期六 16时10分40秒 File Name :code/hdu/1284.cpp …

http://acm.hdu.edu.cn/showproblem.php?pid=2082 题意：26个字母，第i个字母有x[i]个，价值为i.问能组成多少个价值不超过50的单词（注意这里的单词只考虑字母的组成，不考虑字母之间的顺序） 思路：母函数。 /* *********************************************** Author :111qqz Created Time :2016年02月27日 星期六 15时56分31秒 File Name :code/hdu/2082.cpp ************************************************ */ …

http://acm.hdu.edu.cn/showproblem.php?pid=5616 题意：有n个（n<=20）砝码，第i个重量为w[i],给出m个查询，每个查询一个重量，问这个重量能否被称量出。 思路：暴力（没美感），01背包（不会），母函数（瞬间成了傻逼题）和这题很像 hdu1709 balance hdu1709解题报告 /* *********************************************** Author :111qqz Created Time :2016年02月27日 星期六 15时35分32秒 File Name :code/hdu/5616.cpp …

http://acm.hdu.edu.cn/showproblem.php?pid=2152 题意：中文题目，大概是说有n（<=100）种水果，第i种至少拿l[i]个，最多拿r[i]个，现在挑选m种水果组成一个果盘，问方案数。 思路：母函数，之前的题目都是只对上界有限制，其实对下界有限制是一样的。以及。。。一开始以为是拿100元买。。。后来发现是“一打百元大钞”23333 其实再出难点可以对个数以及钱数都有限制。。。。 /* *********************************************** Author :111qqz Created Time :2016年02月27日 星期六 15时14分12 …

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了） 如果转移的时候需要需要加一层硬币的个数。具体见代码。 /* …

http://acm.hdu.edu.cn/showproblem.php?pid=1709 题意：有n个砝码，第i个的重量为w[i]，问从1到sum(所有砝码的重量之和)那些重量无法称量。（所有质量都是整数） 思路：母函数。 一个砝码可以看做有三种状态，放，放左边（+），放右边（-） 需要注意的一点是放在右边(-)的时候，可能是j-w[i]，也可能是w[i]-j /* *********************************************** Author :111qqz Created Time :2016年02月26日 星期五 17时57分05秒 File Name :code/hdu/1709.cpp …

http://acm.hdu.edu.cn/showproblem.php?pid=2189 题意：n个人可以分成若干组，每组人数都为素数，问有多少种分法。 思路：母函数。先预处理素数，记得多处理一点... /* *********************************************** Author :111qqz Created Time :2016年02月26日 星期五 16时24分17秒 File Name :code/hdu/2189.cpp ************************************************ */ #include …