成都集训test0719

Diavolo / 2023-07-20 / 原文

本场比赛难度还可以，T1和T2还是比较可做。但是题目编排三道计数我真服了。

T3 [JOISC2018] 修行

题目描述

求有多少个长度为 \(n\) 的排列恰好有 \(k\) 个位置满足 \(a_{i}>a_{i+1}\) 。

对于 \(49 \%\) 的数据， \(n \leqslant 3\times 10^3\) ;
对于 \(100 \%\) 的数据，\(n \leqslant 10^5\) 。

思路点拨

部分分

本题的 \(O(n^2)\) 暴力是显然的。考虑动态规划，因为直接做有后效性，所以改成插入制。

定义 \(f_{i,j}\) 表示已经考虑了 \(1\) 到 \(i\) ，有 \(j\) 个位置满足前面比后面大。

转移分两类讨论，\(j\) 是增加还是不增加。有 \(f_{i,j}=f_{i-1,j}\times j+f_{i-1,j-1}\times (i-j+1)\) ，比较好理解，这里不细细讲解。

正解

考虑容斥，令 \(f_{i}\) 表示恰好有 \(i\) 个位置满足前面比后面大， \(g_{i}\) 表示至少有 \(i\) 个位置满足前面比后面大，有：

\[g_{i}=\sum_{i \leqslant j} C_{j}^i f_{j} \]

二项式反演得：

\[f_{i} = \sum_{i \leqslant j} (-1)^{j-i}C_{j}^i g_{j} \]

那么我们考虑 \(g_{i}\) 的一般做法。其实就是盒子与球问题吧，球和盒子都是不同的，具体算的话参考囧仙的博客

\[g_{k}=\sum_{i=0}^{n-k} (-1)^{n-k-i}C_{n-k}^i i^n \]

我们带回一般式：

\[f_{k}=\sum_{k \leqslant i} (-1)^{i-k}C_{k}^ig_{i} \]

\[=\sum_{k \leqslant i} (-1)^{i-k}C_{k}^i\sum_{j=0}^{n-i}(-1)^{n-i-j}C_{n-i}^j j^n \]

有两个 \((-1)^x\) 形式的式子十分烦躁，所以我们考虑转换枚举顺序：

\[=\sum_{i=0}^{n-k}(-1)^{n-k-i}i^n\sum_{k \leqslant j \leqslant n-j} C_{n-j}^i C_{j}^k \]

前边都是快速幂的柿子，我们想后边的卷积： \(\sum_{k \leqslant j \leqslant n-j} C_{n-j}^i C_{j}^k\)

其实它是有组合意义的，就是我们考虑将 \(n+1\) 个数划分成 \(i+k+1\) 三个部分。我们考虑枚举其中的那个断点 \(j\) ,那么左边可以选择 \(C_{j}^{k}\) ，右边可以选择 \(C_{n+1-(j+1)}^{i}=C_{n-j}^{i}\) 。

所以上述的卷积柿子就是 \(C_{n+1}^{i+k+1}\) 。带回原柿：

\[f_{k}=\sum_{i=0}^{n-k}(-1)^{n-k-i}i^n C_{n+1}^{i+k+1} \]