POJ1664 放苹果（母函数）

2023-08-03 08:52:28

放苹果

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 37515		Accepted: 23090

Description

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用一行输出相应的K。

Sample Input

1

7 3

Sample Output

思路：多校见过类似的题目，简单母函数题目，不过比赛的时候，直接给出了解题分析：用的递归写的，感觉不是太理解。

递归：（见注释）

 #include <iostream>

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <string>

 #include <vector>

 #include <set>

 #include <map>

 #include <queue>

 #include <algorithm>

 #include <sstream>

 #include <stack>

 using namespace std;

 #define mem(a,b) memset((a),(b),sizeof(a))

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 #define sz(x) (int)x.size()

 #define all(x) x.begin(),x.end()

 typedef long long ll;

 const int inf = 0x3f3f3f3f;

 const ll INF =0x3f3f3f3f3f3f3f3f;

 const double pi = acos(-1.0);

 const double eps = 1e-;

 const ll mod = 1e9+;

 //head

 int fun(int m, int n) {

     if(n ==  || m == )//如果剩1个盘子 || 没有苹果可以放

         return ;

     if(n > m)//如果盘子多于苹果，相当于去除多余盘子

         return fun(m, m);

     else //前者：所有盘子都有苹果，相当于每一个盘子都拿掉一个。后者：至少有一个空盘子

         return fun(m-n, n) + fun(m, n-);

 }

 int _, n, m;

 int main() {

     for(scanf("%d", &_);_;_--) {

         scanf("%d%d", &m, &n);

         printf("%d\n", fun(m, n));//m个苹果，n个盘子

     }

 }

母函数：

理解母函数就是一道裸题，写出各个式子，然后计算，系数即为答案。

有一点比较难理解。我其实一直以为是k++，因为每一项都是,但是题目说了

1，1，5 和 5，1，1是同一种，所以k++会重复，所以用,这样保证了不会重复。

可以理解为拿几个1，拿几个5，这样就避免了重复。

推荐博客：https://www.cnblogs.com/dolphin0520/archive/2012/11/07/2755080.html

母函数计算理解：http://blog.chinaunix.net/uid-26602509-id-3193699.html

 #include <iostream>

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <string>

 #include <vector>

 #include <set>

 #include <map>

 #include <queue>

 #include <algorithm>

 #include <sstream>

 #include <stack>

 using namespace std;

 #define mem(a,b) memset((a),(b),sizeof(a))

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 #define sz(x) (int)x.size()

 #define all(x) x.begin(),x.end()

 typedef long long ll;

 const int inf = 0x3f3f3f3f;

 const ll INF =0x3f3f3f3f3f3f3f3f;

 const double pi = acos(-1.0);

 const double eps = 1e-;

 const ll mod = 1e9+;

 //head

 int c1[], c2[];//c1存展开式的系数，c2计算时保存

 int _, m, n;

 int main() {

     for(scanf("%d", &_);_;_--) {

         scanf("%d%d", &m, &n);

         for(int i = ; i <= m; i++) {//初始化第一个表达式

             c1[i] = ;

             c2[i] = ;

         }

         for(int i = ; i <= n; i++) {//从第二个开始

             for(int j = ; j <= m; j++) {//已经累乘的式子的第j项

                 for(int k = ; k+j <= m; k += i) {//k += i ！！！

                     c2[j+k] += c1[j];

                 }

             }

             for(int i = ; i <= m; i++) {//更新

                 c1[i] = c2[i];

                 c2[i] = ;

             }

         }

         printf("%d\n", c1[m]);//次数为m的系数即为答案

     }

 }

码农公寓