专栏文章

题解：P5367 【模板】康托展开

IICU_midway_azuma
P5367题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio2wrjc
此快照首次捕获于
2025/12/02 12:29
3 个月前
此快照最后确认于
2025/12/02 12:29
3 个月前
查看原文
康托展开，即求一个排列在其全排列中，按字典序排序后所处的位置。
如，1∼31\sim 3 的全排列中：
CPP
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 3 2 排在第 22 位。
考虑逐位比对的方法：
如对于排列 2 3 1，分析过程如下：
第 11 位是 22，比其更小的数有 11（所有首位小于 22 的排列的字典序一定比 2 3 1 小），该位结果为 1×2!=21\times 2!=2。
第 22 位是 33，比其更小的数有 11 和 22，但 22 我们已经用过了（上一位比 22 更小的已经在上一步被统计过，比 22 更大的不被统计，故这里只统计上一位为 22 的情况），所以比其更小的数有 11 个，该位结果为 1×1!=11\times 1!=1。
最后一位以此类推，没有比 11 更小的数，该位结果为 0×0!=00\times 0!=0。
比 2 3 1 字典序小的排列有 2+1+0=32+1+0=3 个，排在第 44 位。
综上，我们总结：
设排列为 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，rir_i 为 a1,a2,⋯ ,ai−1a_1,a_2,\cdots,a_{i-1} 中小于 aia_i 的数的数量。
则第 ii 位的计算结果为 (ai−ri−1)×(n−i)!(a_i-r_i-1)\times (n-i)!。
(n−i)!(n-i)! 可以用预处理，rir_i 显然可以用权值线段树维护。
于是我们做到了 O(nlog⁡n)O(n\log n) 算出 rr 数组，O(n)O(n) 计算答案，总复杂度 O(nlog⁡n)O(n\log n)。
上代码：
CPP
#include<bits/stdc++.h>
#define mod 998244353 
using namespace std;
int a[1000005];
struct node{
	int val;
}tree[1000005<<2];
void pushup(int p){
	tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
}
void update(int p,int l,int r,int ql,int qr){
	if(l>qr||r<ql)return;
	if(l>=ql&&r<=qr){
		tree[p].val++;
		return;
	}
	int mid=l+r>>1;
	update(p<<1,l,mid,ql,qr);
	update(p<<1|1,mid+1,r,ql,qr);
	pushup(p);
}
int query(int p,int l,int r,int ql,int qr){
	if(l>qr||r<ql)return 0;
	if(l>=ql&&r<=qr){
		return tree[p].val;
	}
	int mid=l+r>>1;
	return query(p<<1,l,mid,ql,qr)+query(p<<1|1,mid+1,r,ql,qr);
}
int f[1000005];
long long c[1000005];
signed main(){
	int n;
	cin>>n;
	c[1]=1;
	c[0]=1;
	for(int i=2;i<=1000000;i++){
		c[i]=c[i-1]*i%mod;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		f[i]=query(1,1,n,1,a[i]-1);
		update(1,1,n,a[i],a[i]);
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=(a[i]-f[i]-1)*c[n-i];
		ans%=mod;
	}
	cout<<(ans+1)%mod;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...