LeetCode刷题【1359】有效的快递序列数目

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

输入：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）之后。

输入：n = 3
输出：90

数学求解推导过程

简单来说，第n对快递在原来的排序中插入放置的情况有先P后D的依赖性，不妨来分析下摆放情况，如上图，分别确定D的位置为蓝色，P的情况为绿色的可能性，

那么总和的结果为

(2n-1) + (2n-2) + (2n-3) + ... + 1

这就是一个从1到(2n-1)的求和过程，转化之后为

(2n-1) * 2n / 2

即

2 * n^2 - n

这是第n对快递的情况，而第(n-1)的情况可以由之前求得，这里简单的用f(n-1)表示

所以最终我们知道

f(n) = f(n-1) * ( 2 * n^2 - n )

这样我们从1开始滚动求解得到f(n)的具体数值中途记得模1e9+7

代码

class Solution {
    public int countOrders(int n) {
        long ans = 1;
        long mod = (long) (1e9+7);
        for (int i = 2; i <= n; i++) {
            ans *= (2 * i * i - i);
            ans %= mod;
        }
        return (int)ans;
    }
}