【题解】P7322 「PMOI-4」排列变换

题目链接（洛谷） ## 题目大意

给定常数$k$。对于一个长度为$n$的排列$a$，定义

$ f(a)={{1 i k} {a_i},{2 i k+1} {a_i},,_{n-k+1 i n} {a_i}} $

对于一个长度为$n$的序列$a$，定义其权值$w(a)$为$a$中不同的数的个数。

求对于长度为$n$的排列$p$，它们的$w(f(p))$之和。

$1\le k\le n\le 5\times {10}^5$

正解

不难发现排列有如下性质：

记$f(a)$的第$i$位为$f(a{)}_i$，如果$f(a{)}_i\ne f(a{)}_{i+1}$，那么这是$f(a{)}_i$的在$f(a)$中最后一次出现。

那么答案就是所有排列中相邻两项不同的个数加上$n!$。

当$f(a{)}_{i-1}<f(a{)}_i$时，长度为$k$的窗口，把第$i-k$项去掉，加入了$i$项，发现最大值变大，也就意味着第$i$项比第$i-1$到$i-k$项都大。

枚举$i$表示产生贡献的那个数，有$\sum _{i=k+1}^n()$。

对于区间$[i-k,i-1]$，我们要从小于$i$的$i-1$个数中选出$k$个放进去并进行排序，有$A_{i-1}^k$种方法。

对区间外部的数排序，有$(n-k-1)!$种方法。

再钦定长度为$k+1$的窗口的相对位置，有$n-k$种选法。

所以这部分为： $$\sum _{i=k+1}^n{A}_{i-1}^k(n-k-1)!(n-k)$$ 同理，当$f(a{)}_{i-1}>f(a{)}_i$时，答案也是上式。

所以最终答案为： $$n!+2\times \sum _{i=k+1}^n{A}_{i-1}^k(n-k-1)!(n-k)$$

考场做法

先写出暴搜做法，打表输出$n,k$和答案，并将同一$n$中的每一项与下面做差：

n k ans diff
2 1 4 2
2 2 2

3 1 18 8
3 2 10 4
3 3 6

4 1 96 40
4 2 56 20 
4 3 36 12
4 4 24

5 1 600 240
5 2 360 120
5 3 240 72
5 4 168 48
5 5 120

观察差值的规律：

每一组$n$值中不同$k$值答案之间的比值相同，且$n$每增加$1$，所有差值都乘$n+1$。

设

$$dif{f}_{i,j}=an{s}_{i,j}-an{s}_{i,j+1},i>j$$ 则有

$$dif{f}_{i,j}=dif{f}_{i-1,j}\times (i+1)$$

所以，对于一个$n$值求解时可以先用$dif{f}_{n-1,1}$到$dif{f}_{n-1,n-2}$推出$dif{f}_{n,1}$到$dif{f}_{n,n-2}$。

又因为可以容易得出$an{s}_{n,1}=n!\ast n$和$an{s}_{n,n}=n!$，所以可以通过$diff$数组递推出$an{s}_{n,1}$到$an{s}_{n,n-1}$，并更新出$dif{f}_{n,n-1}=an{s}_{n,n-1}-an{s}_{n,n}$。

用$c_i$表示$dif{f}_{i+1,i}$，即该值刚被更新出来的时候。

sumc[1] = 2;
c[1] = 2;
for (int i = 3; i <= n; i++) {
    sumc[i - 2] *= i + 1; //sumc是c的前缀和
    c[i - 1] = f[i] * i - sumc[i - 2] - f[i]; //f[i]表示i的阶乘
    sumc[i - 1] = c[i - 1] + sumc[i - 2];
}

接着，让$c_i=diff(n,i)$。

for (int i = 1; i < n; i++) {
    c[i] *= f[n + 1] / f[i + 2];
}

最后直接$O(n)$递推答案即可。