1359:有效的快递序列数目(1722 分)
目录
题目
给你 n
笔订单,每笔订单都需要快递服务。
计算所有有效的 取货 / 交付 可能的顺序,使 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
分析
- 可以递推,第 n 对即是在前 2*(n-1) 个物品的间隔插入两个,根据隔板法,即是 comb(2*n,2)
- 也可以直接先计算所有排列 2n!,再去掉不合法的
- 每一对的顺序固定,都多乘了 2
- 因此除以 2^n 即可
解答
|
|
0 ms