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

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

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

$
f(a)={\max{1 \le i \le k} {a_i},\max{2 \le i \le k+1} {ai},\cdots,\max{n-k+1 \le i \le 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$种选法。

所以这部分为：

同理，当$f(a){i-1}>f(a){i}$时，答案也是上式。

所以最终答案为：

考场做法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$。

设

则有

所以，对于一个$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}$。

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

1
2
3
4
5
6
7
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)$递推答案即可。