题目描述
blablabla
样例公式推导
对于给定的某个序列 s,且序列 s 中的元素两两不等,设 s 的反转序列为 s¯. 记 I(s) 为序列 s 的升序对构成的集合,D(s)为序列 s 的降序对构成的集合. 任取序列 s 中的一个元素对 (a,b),一定有 (a,b)∈I(s)∨(a,b)∈D(s),因此,升序对与降序对的总个数等于元素对的总个数,即 ∣I(s)∣+∣D(s)∣=n(n−1)2.
设 (a,b) 是序列 s 中的一个升序对,则 (b,a) 一定是序列 s¯ 中的一个降序对,反之亦然. 因此,D(s)=I(s¯),故 ∣I(s)∣+∣I(s¯)∣=n(n−1)2.
设 1−n 的所有全排列构成的集合为 P,显然 ∣P∣=n! 且本题的答案 V(P)=∑s∈P∣I(s)∣.
设 P¯= { s¯∣s∈P },由于一个全排列的逆序序列仍是全排序,因此 P=P¯,由此可知 V(P)=V(P¯)=12(V(P)+V(P¯))
=12(∑s∈P∣I(s)∣+∑s¯∈P¯∣I(s¯)∣)=12∑s∈P(∣I(s)∣+∣I(s¯)∣)
=12∑s∈Pn(n−1)2
=14n(n−1)n!
作者:stdt33
链接:https://www.acwing.com/solution/content/223375/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla