1359. Count All Valid Pickup and Delivery Options

题目信息

题号:

1359

难度:

Hard

主题:

组合数学、计数

原题:

LeetCode 1359

重点:

每个订单有一次取件和一次配送,配送必须出现在对应取件之后;统计所有合法事件排列并取模

题目重述

有 n 个不同订单,每个订单 i 包含取件事件 P_i 和配送事件 D_i。需要排列全部 2n 个事件,唯一约束是每个 D_i 必须位于对应 P_i 之后。

请返回合法排列数量对 10^9 + 7 取模后的结果。

1 <= n <= 500。

自建示例

两个订单共有六种合法排列:

输入:n = 2
输出:6
解释:在四个事件的排列中,只保留每个配送位于对应取件之后的情况,共六种。

单个订单顺序唯一:

输入:n = 1
输出:1
解释:只能先取件再配送。