1359. 有效的快递序列数目

Powered by:NEFU AB-IN

Link

1359. 有效的快递序列数目

• 题意

  给你 n 笔订单，每笔订单都需要快递服务。
  请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。
  由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

• 思路

  状态表示: f[i]表示考虑前i笔订单,所有的可能序列
  集合划分: 可以根据第i笔订单的pi和di是否挨着进行划分

  状态计算:
  前i - 1笔订单的序列数目为f[i - 1]

  • 当pi和di挨着,将pi和di看成一个整体,相当于从前面2 * (i - 1)个元素中插入一个元素
    2 * (i - 1)个元素中插入一个元素总共有2 * (i - 1) + 1种插入方式
  • 当pi和di不挨着时,相当于从前面2 * (i - 1)个元素中插入两个元素
    2 * (i - 1)个元素中插入两个元素总共有**C(2 * (i - 1) + 1, 2)**种插入方式

  所以 f[i] = f[i - 1] * (2 * (i - 1) + 1 + C(2 * (i - 1) + 1, 2))
  化简整理可得 f[i] = f[i - 1] * (2 * i - 1) * i

• 代码

  #include 
  using namespace std;
  
  // ---------------------
  #define N n + 100
  #define SZ(X) ((int)(X).size())
  #define int long long
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  static int IOS = []() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      return 0;
  }();
  
  class Solution
  {
    public:
      int countOrders(int n)
      {
          vector<int> f(N);
          const int P = 1e9 + 7;
          f[1] = 1;
          for (int i = 2; i <= n; ++i)
          {
              f[i] = f[i - 1] * (2 * i - 1) * i % P;
          }
          return f[n];
      }
  };
  
  #undef int;
  
  // ---------------------
  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