自动搬运

查看原文

来自洛谷，原作者为

	OIer_Eternity 陪你看日落的人，比日落本身更温柔.

搬运于2025-08-24 22:44:07，当前版本为作者最后更新于2023-01-22 16:30:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\mathrm{Upd~2023.2.3}$：优化了排列数的预处理，并且对 $cnt_1,cnt_2$ 进行了预处理，复杂度由 $O(n^3\log n)$ 降低至 $O(n^3)$，速度快了近一倍。感谢大佬 @0x3b800001 提出的意见~

题意简述

• 对于长度为 $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)$。

代码

#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;
}