Fruit
Problem Description
转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。
于是，很多人们慕名而来，找Lele买水果。
甚至连大名鼎鼎的HDU ACM总教头 lcy 也来了。lcy抛出一打百元大钞，"我要买由M个水果组成的水果拼盘，不过我有个小小的要求，对于每种水果，个数上我有限制，既不能少于某个特定值，也不能大于某个特定值。而且我不要两份一样的拼盘。你随意搭配，你能组出多少种不同的方案，我就买多少份！"
现在就请你帮帮Lele，帮他算一算到底能够卖出多少份水果拼盘给lcy了。
注意，水果是以个为基本单位，不能够再分。对于两种方案，如果各种水果的数目都相同，则认为这两种方案是相同的。
最终Lele拿了这笔钱，又可以继续他的学业了～
Input
本题目包含多组测试，请处理到文件结束(EOF)。
每组测试第一行包括两个正整数N和M(含义见题目描述，0<N,M<=100)
接下来有N行水果的信息，每行两个整数A,B(0<=A<=B<=100)，表示至少要买该水果A个，至多只能买该水果B个。
Output
对于每组测试，在一行里输出总共能够卖的方案数。
题目数据保证这个答案小于10^9
Sample Input
2 3
1 2
1 2
3 5
0 3
0 3
0 3
Sample Output
2
12
Author
Linle
Source
ACM程序设计期末考试——2008-01-02（3 教417）
题目类型：普通母函数
算法分析：本题步长为1，且每一个多项式不都是从指数0开始，需要使用额外的数组存储每个多项式的指数范围，其他的就是直接使用普通母函数求解即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 10000 + 7; const int maxn = 10000 + 66; //coeff数组存储每一指数值下的系数值，temp数组存储当前两个多项式相乘的系数值，ans数组存储各个多项式的个数 long long coeff[maxn], temp[maxn], s[maxn], e[maxn]; void Init () { memset (coeff, 0, sizeof (coeff)); memset (temp, 0, sizeof (temp)); } //在调用GenerFunction之前一定先调用Init函数 void GenerFunction (long long expnum, long long upp)//所有数组的下标从1开始 { for (long long i = s[1]; i <= e[1] * 1; i += 1) //初始化第一个多项式的系数值 coeff[i] = 1; for (long long i = 2; i <= expnum; i++) { for (long long j = 0; j <= upp; j++) { for (long long k = s[i]; j + k <= upp && k <= e[i] * 1; k += 1) temp[k+j] += coeff[j];//x ^ k * x ^ j = x ^ (k + j)的系数值 } for (long long j = 0; j <= upp; j++) { coeff[j] = temp[j]; temp[j] = 0; } } } int main() { // ifstream cin ("aaa.txt"); long long n, m; while (cin >> n >> m) { long long len = 0; for (int i = 1; i <= n;i++) { cin >> s[i] >> e[i]; len += e[i]; } Init (); GenerFunction (n, len); cout << coeff[m] << endl; } return 0; } |
- « 上一篇：hdu2149
- hdu2188：下一篇 »