题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2152

题目描述

转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。

于是,很多人们慕名而来,找Lele买水果。

甚至连大名鼎鼎的HDU ACM总教头 lcy 也来了。lcy抛出一打百元大钞,”我要买由M个水果组成的水果拼盘,不过我有个小小的要求,对于每种水果,个数上我有限制,既不能少于某个特定值,也不能大于某个特定值。而且我不要两份一样的拼盘。你随意搭配,你能组出多少种不同的方案,我就买多少份!”

现在就请你帮帮Lele,帮他算一算到底能够卖出多少份水果拼盘给lcy了。

注意,水果是以个为基本单位,不能够再分。对于两种方案,如果各种水果的数目都相同,则认为这两种方案是相同的。

最终Lele拿了这笔钱,又可以继续他的学业了~

思路

这题有点特殊,母函数每个表达式不是$x^0$开头,而是$x^{A_i}$到$x^{B_i}$,因为要求数量是从$A_i$到$B_i$

即$\left(x^{A_1}+x^{A_1+1}+x^{A_1+2}+\dots+x^{B_1}\right) \left(x^{A_2}+x^{A_2+1}+x^{A_2+2}+\dots+x^{B_2}\right)+\dots+\\ \left(x^{A_N}+x^{A_N+1}+\dots+x^{A_N+2}+\dots+x^{B_N}\right)$

展开后$x^M$的系数即为答案。

AC代码

/*************************************************************************
    > File Name: 2152.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-04 Sat 10:57:49 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
struct f {
    int min, max;
} f[101];

int main()
{
#ifdef Oj
    freopen("2152.in", "r", stdin);
#endif
    int n,m;
    int c1[101], c2[101];
    while(cin >> n >> m) {
        for(int i=1; i<=n; ++i)
            cin >> f[i].min >> f[i].max;
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        for(int i=f[1].min; i<=f[1].max; ++i)
            c1[i] = 1;

        for(int i=2; i<=n; ++i) {
            for(int j=0; j<=m; ++j) {
                for(int k=f[i].min;(j+k<=m)&& k<=f[i].max; ++k)
                    c2[j+k] += c1[j];
            }
            for(int j=0; j<=m; ++j) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout << c1[m] << endl;

    }

    return 0;
}