微积分习题

小王是大一的学生，想在寒假里强化一下微积分课程的学习，他从图书馆借了一套吉米多维奇的数学分析习题集。他决定在以后的 n 天里要做完上面的 S 道积分题。

为了能够尽快地完成任务，小王强迫自己第 i 天至少要做 a_i 道积分题。但是，小王在假期里还有其他事情（例如过春节），每天的题量不能太多，他估计了一下，第 i 天做的积分题不能超过 b_i （ b_i ≥ a_i ）道。

现在小王想知道，究竟能有多少种方案能够在 n 天里做完这 S 道习题呢？小王请你写个程序帮他算一算。

具体来说，一个方案就是每天做的微积分题的数目的序列，假设第 i 天完成 x_i 道题（ x_i 当然满足 a_i ≤ x_i ≤ b_i ，且 x ₁ +x₂+……+x_n=S ）。那么向量 (x₁, x_2, …, x_n) 就对应了一个方案。两个方案不同是指它们对应的向量不同。

【输入】

一共 n +1 行，第一行是两个整数 n 和 S ，用空格分开，分别表示天数和题目数（ 1 ≤ n ≤ 20 ， 1 ≤ S ≤ 1000 ）；接下来 n 行每行两个整数，之间用空格隔开，分别表示第 i 天对做题数量的限制 a_i 和 b_i （ 0 ≤ a_i ≤ b_i ≤ S ）。

【输出】

一个整数，表示满足条件的方案数 T 。

【输入输出】

 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

class BigNum
{
 vector<int> val;
public:
 static const int NUM = 10000;
 static const int WIDTH = 4;
 BigNum(int n = 0);
 friend ostream& operator << (ostream &out, const BigNum &n);
 bool operator != (const BigNum &n) const {return val != n.val;}
 BigNum& operator += (const BigNum &n2);
};
BigNum::BigNum(int n /* = 0 */)
{
 do // 保证val至少有一个元素
 {
  int a = n / NUM;
  int b = n % NUM;
  val.push_back(b);
  n = a;
 } while(n > 0);
}

BigNum& BigNum::operator += (const BigNum &n2)
{
 if (val.size() < n2.val.size()) // n2短
  val.resize(n2.val.size());
 transform(n2.val.begin(), n2.val.end(), val.begin(), val.begin(), plus<int>());
 int lastAdd = 0;
 for (vector<int>::iterator it = val.begin(); it != val.end(); ++it)
 {
  *it += lastAdd;
  if (*it >= BigNum::NUM)
  {
   *it -= BigNum::NUM;
   lastAdd = 1;
  }
  else
   lastAdd = 0;
 }
 if (lastAdd == 1)
  val.push_back(1);
 return *this;
}
ostream& operator << (ostream &out, const BigNum &n)
{
 if (n.val.size() == 1)  // 只有一个数
  return out << n.val[0];
 out << n.val.back();
 char c = out.fill('0');
 for (vector<int>::const_reverse_iterator it = n.val.rbegin()+1;
  it != n.val.rend(); ++it)
  out << setw(BigNum::WIDTH) << *it;
 return out << setfill(c);
}
#if 1 // 记录表法
const int MAX_N = 20;
const int MAX_S = 1000;
int n, S;
int a[MAX_N], b[MAX_N];
BigNum T[MAX_N][MAX_S + 1] = {{0}}; // 记录表

BigNum Cal(int day, int done, int min, int max)
{
 int left = S - done;   // 还有多少题要做
 if (left < min || left > max) // 超出可能的做题范围
  return 0;     // 方案必不成功，部分方案数为0
 if (day == n - 1)    // 最后一天，方案必然可能
  return 1;     // 部分方案数为1，递归终止

 if (T[day][done] != 0)   // 已经计算过
  return T[day][done];
 BigNum total = 0;    // 部分方案数
 for (int t = a[day]; t <= b[day]; t++)   // 枚举
  total += Cal(day + 1, done + t, min-a[day], max-b[day]); // 递归计算
 T[day][done] = total;   // 记录下来
 return total;
}

int main()
{
 // 读入数据
 cin >> n >> S;
 for (int i = 0; i < n; i++)
  cin >> a[i] >> b[i];

 int min = 0, max = 0;  // 最少和最多做题数量
 for (int i = 0; i < n; i++)
 {
  min += a[i];
  max += b[i];
 }
 cout << Cal(0, 0, min, max) << endl;
 return 0;
}

#else // 动态规划算法
const int MAX_N = 20;
const int MAX_S = 1000;
int n, S;
int a[MAX_N], b[MAX_N];
BigNum fa[MAX_N][MAX_S+1];

int main()
{
 // 读入数据
 cin >> n >> S;
 for (int i = 0; i < n; i++)
  cin >> a[i] >> b[i];

 int leftMin = 0, leftMax = 0; // 还剩下的天中最少和最多做题数
 for (int i = 0; i < n; i++)
 {
  leftMin += a[i];
  leftMax += b[i];
 }

 // 第0天
 int realMin = a[0], realMax = b[0]; // 到当前天为止，最少和最多做题数
 leftMin -= a[0]; leftMax -= b[0];
 if (realMin < S - leftMax) realMin = S - leftMax;
 if (realMax > S - leftMin) realMax = S - leftMin;
 for (int t = realMin; t <= realMax; t++)
  fa[0][t] = 1;

 for (int day = 1; day < n; day++)
 {
  realMin += a[day]; realMax += b[day];
  leftMin -= a[day]; leftMax -= b[day];
  if (realMin < S - leftMax) realMin = S - leftMax;
  if (realMax > S - leftMin) realMax = S - leftMin;

  for (int tall = realMin; tall <= realMax; tall++) // 对于总题量
   for (int t = a[day]; t <= b[day] && t <= tall; t++)
    fa[day][tall] += fa[day-1][tall-t]; // 累计之前的可能方案数
 }
 cout << fa[n-1][S] << endl;
 return 0;
}
#endif