1359-有效的快递序列数目

给你 n 笔订单，每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

示例 1：

**输入：** n = 1
**输出：** 1
**解释：** 只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。

示例 2：

**输入：** n = 2
**输出：** 6
**解释：** 所有可能的序列包括：
(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。

示例 3：

**输入：** n = 3
**输出：** 90

提示：

• 1 <= n <= 500

方法一：递推法

设 f[i] 表示订单数量为 i 时的序列数目，我们希望通过 f[1], f[2], ..., f[i - 1] 得到 f[i] 的值，这样就可以使用递推的方法得到 f[n] 了。

由于 f[i] 包含了 i 份订单，我们可以将其拆分为前 i - 1 份订单（编号为 1, 2, ..., i - 1）与 1 份额外的订单（编号为 i）。对于一个包含前 i - 1 份订单的固定序列，它的长度为 (i - 1) * 2，我们只需要在这个序列中加上第 i 份订单，就可以得到一条订单数量为 i 的序列。

那么有多少种不同的方法能够加上第 i 份订单呢？第 i 份订单包含 P_i 和 D_i，并且 P_i 在序列中必须出现在 D_i 之前，那么我们可以将这些方法分成两类：

• 第一类：P_i 和 D_i 被添加到了序列中连续的位置。由于序列的长度为 (i - 1) * 2，那么可以添加的位置为序列的长度加 1，即 2(i - 1) + 1 = 2i - 1；

• 第二类：P_i 和 D_i 被添加到了序列中不连续的位置，那么就相当于在 i * 2 - 1 个位置中选择两个不同的位置，前者用作添加 P_i，后者用作添加 D_i，方法数为组合数 \binom{2i - 1/2} = (2i - 1)(i - 1)。

将这两类的方法数量相加，就可以得到：对于一个固定的包含前 i - 1 份订单的固定序列，用 (2i-1)i 种方法可以加入第 i 份订单。由于前 i - 1 份订单对应的序列数目为 f[i - 1]，并且对于任意两个不同的包含前 i - 1 份订单的序列，都不会因为加上第 i 份订单使得它们变得相同。因此我们就得到了递推公式

f[i] = (2i-1)i * f[i - 1]

由于递推公式中 f[i] 仅与 f[i - 1] 有关，我们在递推式可以只存储 f[i - 1] 的值，而不用把 f[1], f[2], ..., f[i - 1] 都记录下来。

[sol1-C++]

using LL = long long;

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int countOrders(int n) {
        if (n == 1) {
            return 1;
        }
        int ans = 1;
        for (int i = 2; i <= n; ++i) {
            ans = (LL)ans * (i * 2 - 1) % mod * i % mod;
        }
        return ans;
    }
};

[sol1-Python3]

class Solution:
    def countOrders(self, n: int) -> int:
        if n == 1:
            return 1
        ans, mod = 1, int(1e9 + 7)
        for i in range(2, n + 1):
            ans = ans * (i * 2 - 1) * i % mod
        return ans

复杂度分析

• 时间复杂度：O(N)。

• 空间复杂度：O(1)。

方法二：整体法

除了递推法之外，我们也可以从整体进行考虑，直接得到 f[i] 的通项公式。

假设现在没有 D_i 必须在 P_i 之后的要求，那么

f[i] = (2i)!

这是因为我们可以将 P_1, D_1, P_2, D_2, \cdots, P_i, D_i 的任意一个排列作为答案，排列的数目为 (2i)!。我们称这些排列为初始排列。

那么在加上了「D_i 必须在 P_i 之后」的要求后，有一些初始排列就不能作为答案了。但是我们可以对它们进行调整，使它们变成满足要求的排列。具体地，对于任意一个初始排列，如果第 j 个物品的 D_j 出现在 P_j 之前，那么我们就把 D_j 和 P_j 交换顺序。在对 j = 1, 2, ..., i 全部判断一遍之后，我们就可以得到一个满足要求的排列了。然而这样会导致重复计数，这是因为不同的初始排列在交换顺序之后会得到相同的排列，例如当 i = 2 时，初始排列

D1, D2, P1, P2
D1, P2, P1, D2

在交换后都会得到相同的排列

P1, P2, D1, D2

如何去除重复计数呢？我们可以进行逆向思考，反过来计算一个排列可以从多少个初始排列得来。显然，对于排列中的 i 对 P_j 和 D_j，我们将其中任意数量的对交换顺序，都可以得到一个不同的初始排列。交换顺序的选择有 2^i 种（每一对 P_j 和 D_j 交换或不交换），因此一个排列对应着 2^i 个初始排列，即排列的数目为：

f[i] = (2i)!}{2^i}

这样就得到了 f[i] 的通项公式。由于通项公式中包含除法，在取模的意义下不好直接计算，我们可以将分母 2^i 拆分成 i 个 2，与分子阶乘中的 i 个偶数相除，得到

f[i] = i!(2i-1)!!

其中 (2i-1)!! = 1 \cdot 3 \cdot \cdots \cdot (2i-1)，其与方法一中的递推式是一致的，可以直接使用方法一的代码。

复杂度分析

• 时间复杂度：O(N)。

• 空间复杂度：O(1)。