AC6 Round B sol
Sol1
·
·
题解
upd. 把那个大公式改得稍微好看一点…要不然太长了
idea 为原题改编
设 I 为全局逆序对数量，以及：
\begin{cases}f(n)=\sum_{i=0}^n[n]_i\\g(n)=\sum_{i=0}^n(i+1)[n]_i\\h(n)=\sum_{i=0}^n(i+1)^2[n]_i\end{cases}
其中 f,g,h 均有线性递推式：
\begin{cases}f(n)=1+nf(n-1)\\g(n)=1+n[g(n-1)+f(n-1)]\\h(n)=1+n[h(n-1)+2g(n-1)+f(n-1)]\end{cases}
对于 i<j\leq n，考虑在哪些方案中 a_i 和 a_j 会被交换。
情况 1：子序列中同时出现 i,j，且重新排列之后 j 换到 i 前面。
考虑枚举子序列长度，得到方案数为：
\begin{aligned}&\sum_{k=0}^{n-2}\binom{n-2}{k}\cdot \dfrac{(k+2)!}{2}\\=&\sum_{k=0}^{n-2}\dfrac{(n-2)!}{k!(n-2-k)!}\cdot\dfrac{k!\cdot(k+1)\cdot(k+2)}{2}\\=&\sum_{k=0}^{n-2}\dfrac{(k+1)\cdot(k+2)}{2}[n-2]_k\\=&\dfrac{g(n-2)+h(n-2)}{2}\end{aligned}
情况 2：i 在子序列里面，j 不在子序列里面，重新排列后 i 被放到了 j 后面。
考虑枚举有几个子序列的元素出现在 j 前面，以及有几个出现在 j 后面。
得到下式：
\sum_{k=1}^{n-j}\sum_{l=0}^{j-2}\binom{n-j}{k}\binom{j-2}{l}k(k+l)!
拆定义式变形：
\sum_{k=1}^{n-j}\sum_{l=0}^{j-2}\dfrac{(n-j)!}{k!(n-j-k)!}\cdot\dfrac{(j-2)!}{l!(j-l-2)!}\cdot k(k+l)!
提出 n-j，约去 k：
(n-j)\sum_{k=1}^{n-j}\sum_{l=0}^{j-2}\dfrac{(n-j-1)!}{(k-1)!(n-j-k)!}\cdot\dfrac{(j-2)!}{l!(j-l-2)!}\cdot (k+l)!
组合数定义式变形：
(n-j)\sum_{k=0}^{n-j-1}\sum_{l=0}^{j-2}\binom{n-j-1}{k}\binom{j-2}{l}(k+l+1)!
调换枚举顺序（先枚举 k+l）：
(n-j)\sum_{k=0}^{n-3}(k+1)!\sum_{l=0}^{j-2}\dbinom{n-j-1}{k-l}\dbinom{j-2}{l}
沃德你蒙德恒等式变形：
(n-j)\sum_{k=0}^{n-3}(k+1)!\dbinom{n-3}{k}
拆定义式变形：
(n-j)\sum_{k=0}^{n-3}(k+1)[n-3]_k
代入预设函数：
(n-j)g(n-3)
情况 3：j 在子序列里面，i 不在子序列里面，重新排列后 j 被放到了 i 前面。
类似情况 2 可以得到情况数为 (i-1)g(n-3)
全部合起来再加上全局逆序对的贡献就得到区间 [1,n] 的答案式：
\text{Ans}(1,n)=f(n)\cdot I-\sum_{i=1}^n\sum_{j=i+1}^n \operatorname{sgn}(a_i-a_j)\cdot\left[\dfrac{h(n-2)+g(n-2)}{2}+(i-1+n-j)g(n-3)\right]
预处理 f,g,h，树状数组即可。
复杂度 O(n\log n)。