P8962 「WHOI-4」C yadiw. Slua, gassp, lhtubs. 题解
OIer_Eternity
·
·
题解
### 题意简述
- 对于长度为 $i\in[1,n]$ 的一个 $[1,i]$ 的无序排列，求能够通过二分的方法查询到第 $k\in[1,i]$ 小的元素的序列个数。
- $10\le n\le400$，答案对给定的 $2\le p\le998244353$ 取模（$p$ 不一定为质数）。
### 题目分析
首先我们考虑，若需要正确地找到第 $k$ 小的元素（我们称之为 $x$），则对于每一个 $Mid$，$a_{Mid}$ 与 $x$ 的大小关系是确定的。
换言之，若 $x$ 位于位置 $p$，我们可以模拟二分的过程：
对于当前的 $Mid$，若 $p<Mid$ 则必然 $a_{Mid}>x$，若 $p>Mid$ 则必然 $a_{Mid}<x$，否则已经找到了 $x$。
那么我们就能求出 $a$ 数列中，必须小于 $x$ 以及必须大于 $x$ 的数的个数，分别记作 $cnt_1$ 和 $cnt_2$，则大小关系与 $x$ 不确定的个数为 $n-cnt_1-cnt_2-1$（总数减小于减大于减等于的个数），其中 $n$ 为数列长度。则满足此大小关系的数列的个数为：$A_{x-1}^{cnt_1}\times A_{n-x}^{cnt_2}\times A_{n-cnt_1-cnt_2-1}^{n-cnt_1-cnt_2-1}\bmod p$。
则我们可以设立三层循环：第一层循环 $i\in[1,n]$ 表示数列长度，第二层循环 $j\in[1,i]$ 表示需要找到第 $j$ 大的元素，第三层循环 $k\in[1,i]$ 表示第 $j$ 大元素位于位置 $k$ 时的方案数。若设 $ans_{(i,j)}$ 为输出中第 $i$ 行第 $j$ 列，则
$$
ans_{(i,j)}=\Big(\sum_{k=1}^iA_{j-1}^{cnt_1}\times A_{i-j}^{cnt_2}\times A_{i-cnt_1-cnt_2-1}^{i-cnt_1-cnt_2-1}\Big)\bmod p
$$
若我们暴力求$ A$，那么复杂度会达到 $O(n^4\log n)$，显然不行；那么我们可以 $O(n^2)$ 预处理出 $\forall i\in[1,n],j\in[1,i]$，$C_i^j$ 的值，$O(n)$ 预处理出 $\forall i\in[1,n]$，$i!$ 的值，再结合排列数和阶乘 $O(n^2)$ 预处理出 $A_i^j=C_i^j\times j!$ 降低复杂度即可。并且可以$O(n^2\log n)$ 预处理出 $cnt_1,cnt_2$ ，最终复杂度为 $O(n^3)$。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int p,n,C[500][500],frac[500]={1},A[500][500],cnt1[500][500],cnt2[500][500]; // cnt1表示<的个数 cnt2表示>的个数
int main(){
scanf("%d%d",&p,&n);
for (int i=1;i<=n;i++) frac[i]=1ll*frac[i-1]*i%p; // 预处理阶乘
for (int i=0;i<=n;i++) C[i][0]=C[i][i]=1;
for (int i=1;i<=n;i++) for (int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p; // 预处理组合数
for (int i=0;i<=n;i++) for (int j=0;j<=i;j++) A[i][j]=1ll*C[i][j]*frac[j]%p; // 组合数*阶乘=排列数
for (int i=1;i<=n;i++) // 预处理 cnt1,cnt2
for (int k=1;k<=i;k++){
int L=1,R=i;
while (L<R){
int Mid=(L+R)>>1;
if (k==Mid) break;
if (k<Mid) cnt2[i][k]++,R=Mid-1;
else cnt1[i][k]++,L=Mid+1;
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=i;j++){
int cnt=0;
// i个元素中,j位于k时能够找到j的方案数
for (int k=1;k<=i;k++) cnt=(cnt+1ll*A[j-1][cnt1[i][k]]*A[i-j][cnt2[i][k]]%p*A[i-cnt1[i][k]-cnt2[i][k]-1][i-cnt1[i][k]-cnt2[i][k]-1]%p)%p;
printf("%d ",cnt);
}
puts("");
}
return 0;
}
```