AcWing秋招每日一题——week4

Mon

题目

有效的快速序列数目

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

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

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

代码

class Solution {
public:
    int mod = 1000000007;

    long f(int i){
        if(i==1){return 1;}
        return i*(2*i-1)*f(i-1)%mod;
    };

    int countOrders(int n) {
        return f(n);
    }
};

思路解析

n笔订单，一共有2n个数据（p1,d1,p2,d2......pn,dn），所以排列共有2n!种。但是其中存在不符合题目要求的排列，所以为了获得正确的数据，需要将这些去除。可以知道，一个符合条件的长度为2n的排列可以2ⁿ个排列得来，所以排列共有2n！/2ⁿ个。