欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu2079选课时间解题报告---母函数/生成函数(组合数学)

程序员文章站 2022-05-14 18:15:55
...

                                             选课时间

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7621    Accepted Submission(s): 5535


 

Problem Description

又到了选课的时间了,xhd看着选课表发呆,为了想让下一学期好过点,他想知道学n个学分共有多少组合。你来帮帮他吧。(xhd认为一样学分的课没区别)

Input

输入数据的第一行是一个数据T,表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40),k(1 <= k <= 8)。
接着有k行,每行有两个整数a(1 <= a <= 8),b(1 <= b <= 10),表示学分为a的课有b门。

Output

对于每组输入数据,输出一个整数,表示学n个学分的组合数。

Sample Input

2

2 2

1 2

2 1

40 8

1 1

2 2

3 2

4 2

5 8

6 9

7 6

8 8

Sample Output

2

445

思路:组合问题, 母函数/生成函数模板来解决。

AC Code:

#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<list>
#define mod 998244353
#define INF 0x3f3f3f3f
#define Min 0xc0c0c0c0
#define mst(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, k;
        scanf("%d%d", &n, &k);
        int c1[45] = {0}, c2[45] = {0};
        int a[10], b[15];
        for(int i = 1; i <= k; i++){
            scanf("%d%d", &a[i], &b[i]);
        }
        for(int i = 0, t = 0; i <= n && t <= b[1]; i += a[1], t++){
            c1[i] = 1;
        }
        for(int i = 2; i <= k; i++){ 
            for(int j = 0; j <= n; j++){    
                for(int t = 0, w = 0; j + t <= n && w <= b[i]; t += a[i], w++){
                    c2[j + t] += c1[j];
                }
            }
            for(int j = 0; j <= n; j++){
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        printf("%d\n", c1[n]);
    }
    return 0;
}

 

相关标签: hdu