算法:排列组合
-
根据高中数学知识,这题就是在 $2n$ 个位置上两两插入数字,所以直接用公式 $C^2_{2n}$ $\times$ $C^2_{2n - 2}$ $\times$ $…$ $\times$ $C^2_2$,而且不用提前预处理组合数(我傻了前面预处理了一下,直接双 $5\%$,笑拉了),
因为 $C^2_k$ $=$ $k$ $\times$ $(k - 1)$ $/$ $2$,所以直接枚举即可 -
这题因为每次插入的两个数字之间的位置关系已经固定好了,所以用组合数;而组合数这样相乘就已经自带了顺序,本题中要求的就是需要有顺序;如果是取消顺序,那就是分堆问题了:比如说把六个小球分成两堆有几种分法,其中一类就是两堆各三个,这时候这一类的结果就是 $C^3_6$ $\times$ $C^3_3$ $/$ $A^2_2$
时间复杂度 $O(n)$
顺带一提,这题位运算提速非常明显
空间复杂度 $O(1)$
C++ 代码
typedef long long LL;
const int MOD = 1e9 + 7;
class Solution {
public:
int countOrders(int n) {
LL res = 1;
n <<= 1;
for (int i = n; i; i -= 2)
res = (res * i * (i - 1) >> 1) % MOD;
return res;
}
};