欢迎访问==> 【考研OR保研】机试题
给你 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
C++代码
/*
状态表示:f[i]表示考虑前i笔订单,所有的可能序列
集合划分:可以根据第i笔订单的pi和di是否挨着进行划分
状态计算:
前【i - 1】笔订单的序列数目为f[i - 1]
1、当pi和di挨着,将pi和di看成一个整体,相当于从前面2 * (i - 1)个元素中插入一个元素
2 * (i - 1)个元素中插入一个元素总共有【2 * (i - 1) + 1】种插入方式
2、当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】
*/
const int N = 510, P = 1e9 + 7;
long long f[N];
class Solution {
public:
int countOrders(int n) {
f[1] = 1;
for(int i = 2; i <= n; i ++)
{
f[i] = f[i - 1] * (2 * i - 1) * i % P;
}
return f[n];
}
};
牛啊