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

发表于 2021-08-25 分类于信息学阅读次数： Valine：

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

给定常数$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 \neq 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$。

设

\[ diff_{i,j}=ans_{i,j}-ans_{i,j+1},i>j \] 则有

\[ diff_{i,j}=diff_{i-1,j}\times (i+1) \]

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

又因为可以容易得出$ans_{n,1}=n!*n$和$ans_{n,n}=n!$，所以可以通过$diff$数组递推出$ans_{n,1}$到$ans_{n,n-1}$，并更新出$diff_{n,n-1}=ans_{n,n-1}-ans_{n,n}$。

用$c_i$表示$diff_{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)$。

1
2
3

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

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