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).
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)是不同的方法。
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)
指数型母函数网上的资料不是很多，推荐毛杰明的09年国家集训队论文《母函数的性质及应用》
以及Richard A.Brualdi 所著的《组合数学》的第七章来看…倒不用全看懂..但是这本上面干货比较多。
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=3734
题意+思路同******hdu2065红色病毒解题报告
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月27日 星期六 16时39分53秒 4File Name :code/poj/3734.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const LL MOD =1E4+7; 34LL n; 35LL res; 36LL ksm(LL a,LL b) 37{ 38 LL res = 1; 39 while (b) 40 { 41 if (b&1) res=(res*a)%MOD; 42 b = b>>1; 43 a = (a*a)%MOD; 44 } 45 return res; 46} 47int main() 48{ 49 #ifndef ONLINE_JUDGE 50 freopen("code/in.txt","r",stdin); 51 #endif 52 53 54 int T; 55 cin>>T; 56 while (T--) 57 { 58 scanf("%lld",&n); 59 60 LL ans = ksm(4,n-1)+ksm(2,n-1); 61 ans %=MOD; 62 printf("%lld\n",ans); 63 64 } 65 66 67 68 #ifndef ONLINE_JUDGE 69 fclose(stdin); 70 #endif 71 return 0; 72}
http://acm.hdu.edu.cn/showproblem.php?pid=2065 题意：a,b,c,d四种元素，a,c只能出现偶数次（包括0次），b,d没有限制，问n个（2^64）个元素有多少种不同的组合。 思路：指数型母函数。。。n大的没办法用之前的办法做。
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）分钱的方案数。 思路：母函数.
需要注意的是多组数据。每次都搞会TLE，可以先预处理出来存到数组里，每次直接调用。如果预处理时间也还是慢的话，可以先跑出来，然后打表。这算一个小tip吧2333
http://acm.hdu.edu.cn/showproblem.php?pid=2082 题意：26个字母，第i个字母有x[i]个，价值为i.问能组成多少个价值不超过50的单词（注意这里的单词只考虑字母的组成，不考虑字母之间的顺序） 思路：母函数。
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月27日 星期六 15时56分31秒 4File Name :code/hdu/2082.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4; 34LL a[N],tmp[N]; 35int x[N]; 36int n; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 43 44 ios::sync_with_stdio(false); 45 int T; 46 cin>>T; 47 while (T--) 48 { 49 for ( int i = 1; i <= 26 ; i ++) cin>>x[i]; 50 51 ms(tmp,0); 52 ms(a,0); 53 for ( int i = 0 ; i <= x[1]; i++) 54 { 55 a[i] = 1; 56 } 57 // cout<<"aaa"<<endl; 58 int cur = x[1]*1; 59 for ( int i = 2 ; i <= 26 ; i++) 60 { 61 for ( int j = 0 ; j<= cur ; j++) 62 { 63 for ( int k = 0 ; k <= x[i] ; k++) 64 { 65 tmp[j+i*k]+=a[j]; 66 } 67 } 68 69 cur += x[i]*i; 70 71 // cout<<"bbb:"<<endl; 72 73 for ( int j = 0 ; j <= cur ; j++) 74 { 75 a[j] = tmp[j]; 76 tmp[j] = 0 ; 77 } 78 } 79 // cout<<"asdsad"<<endl; 80 LL ans = 0LL ; 81 for ( int j = 1 ; j <= 50 ; j++) 82 { 83 ans += a[j]; 84 } 85 cout<<ans<<endl; 86 } 87 88 #ifndef ONLINE_JUDGE 89 fclose(stdin); 90 #endif 91 return 0; 92}
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种水果组成一个果盘，问方案数。
思路：母函数，之前的题目都是只对上界有限制，其实对下界有限制是一样的。以及。。。一开始以为是拿100元买。。。后来发现是“一打百元大钞”23333 其实再出难点可以对个数以及钱数都有限制。。。。
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个人可以分成若干组，每组人数都为素数，问有多少种分法。 思路：母函数。先预处理素数，记得多处理一点…
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月26日 星期五 16时24分17秒 4File Name :code/hdu/2189.cpp 5************************************************ */ 6 7#include <cstdio>muhanshu 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=155; 34int pri[N]; 35int a[N],tmp[N]; 36int cnt; 37int n; 38 39bool judge ( int n) 40{ 41 if (n<=3) return true; 42 for ( int i = 2 ; i*i <= n ; i++) 43 { 44 if (n%i==0) return false; 45 } 46 47 return true; 48} 49 50 51void pre() 52{ 53 cnt = 0; 54 for ( int i = 2 ; i <= 200 ; i++) 55 { 56 if (judge(i)) 57 pri[++cnt] = i; 58 } 59} 60int main() 61{ 62 #ifndef ONLINE_JUDGE 63 freopen("code/in.txt","r",stdin); 64 #endif 65 66 67 int T; 68 pre(); 69 scanf("%d",&T); 70 while (T--) 71 { 72 scanf("%d",&n); 73 74 ms(a,0); 75 for ( int i = 0 ; i <= n ; i+=2 ) 76 { 77 a[i] = 1; 78 tmp[i] = 0; 79 } 80 81 82 for ( int i = 2 ; pri[i] <= n ; i++) 83 { 84 for ( int j = 0 ; j <= n ; j++) 85 { 86 for ( int k = 0 ; k + j <= n ; k +=pri[i]) 87 { 88 tmp[j+k] +=a[j]; 89 } 90 } 91 for ( int j = 0 ; j <= n ; j ++) 92 { 93 a[j] = tmp[j]; 94 tmp[j] = 0; 95 } 96 } 97 98 printf("%d\n",a[n]); 99 } 100 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105}
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的就是答案。
http://acm.hdu.edu.cn/showproblem.php?pid=1398 题意：所有的货币都是平方数，比如1,4,9…问凑出n块钱有多少种办法。 思路：母函数。
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月25日 星期四 22时15分31秒 4File Name :code/hdu/1398.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=305; 34int a[N],tmp[N]; 35int n; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 while (scanf("%d",&n)!=EOF&&n) 43 { 44 for (int i = 0 ; i <= n ;i++) 45 { 46 a[i] = 1; 47 tmp[i] = 0 ; 48 } 49 50 for ( int i = 2 ; i*i <= n ; i ++) 51 { 52 for ( int j = 0 ; j <= n ; j++) 53 { 54 for ( int k = 0 ; k+j <= n ; k+=i*i) 55 { 56 tmp[j+k] += a[j]; 57 } 58 } 59 60 for ( int j = 0 ; j <= n ;j++) 61 { 62 a[j] = tmp[j]; 63 tmp[j] = 0 ; 64 } 65 } 66 67 printf("%d\n",a[n]); 68 } 69 70 #ifndef ONLINE_JUDGE 71 fclose(stdin); 72 #endif 73 return 0; 74}
http://acm.hdu.edu.cn/showproblem.php?pid=1028 题意：求整数拆分数。 思路：母函数模板题。关于母函数的学习：http://www.cnblogs.com/syxchina/archive/2011/07/07/2197205.html http://www.cppblog.com/tanky-woo/archive/2010/08/02/121969.html
