【题解】Solution Set - NOIP2024模拟赛4

https://www.becoder.com.cn/contest/5501

T2 沉默乐团

https://www.becoder.com.cn/submission/2593352

T3 深黯「军团」

记录一下考场思路：

首先对于长度为 \(n\) 所有排列，按顺序求出她的逆序对数量。然后找到了规律。

后面基于此，写出来可以根据长度和康托展开的编号求出逆序对前缀和的函数。

按道理这样就可解了，但是康托展开的结果太大了，达到了 \(500000!\) 的量级，实际上根本无法直接处理。

所以就完全破产了。

https://www.becoder.com.cn/submission/2593271

由于 \(k\) 很小，所以后面就整了一个可以求前缀后缀和的东西，然后算了一下。

一个结论：

所有 \(1\sim n\) 的排列的逆序对之和为 \(n!\dfrac {n(n-1)}4\)。

（其实这个就是当时考场代码求的 \(f_n\) 数组。

但是问题还是求一个排列的前缀逆序对之和。

首先需要拆成 \(n\) 位，每位的贡献就是后面比她小的数的个数，设成一个序列 \(b\)。然后有两种做法：

1. 用康托展开来理解，那么这相当于一个不等进制数（想到过拆位算贡献，但是这个东西没见过啊
   标签：Set,题解,Solution,becoder,逆序,NOIP2024,康托
   From： https://www.cnblogs.com/CloudWings/p/18391146