康托展开模板

康托展开

https://www.luogu.org/problem/P5367

注:看到名字不觉就想到"好康"

即求一个序列(不重复元素)在其所有排列中的排名

问题转化成比他小的有多少个

实体化

一个序列 A[]=2 4 5 3 1下标分别为1,2,3,4,5

假如

第一个位置比2(A[1])小的话,后面怎么排都是比他小的(n-1)!

这样就有1*(n-1)!个了,

前一个1是指比2小的只有一个数

后一个指后面排列的方案数

再考虑第二个位置4(A[2]),

比他小的,除了它前面出现的2以外,还有2个数(1,3)

为什么要排除以前出现过比他小的呢?

其实很好理解,

就是数位dp中记忆化搜索的顶着上界

code by wzxbeliever

#include<bits/stdc++.h>
#define ll long long
#define ri register int
#define il inline
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=1000005;
const int mod=998244353;
int n; 
ll ans;
ll fac[maxn];
int a[maxn],c[maxn];
void add(int x,int p){while(x<=n)c[x]+=p,x+=lowbit(x);return;}
int query(int x){int res=0;while(x)res+=c[x],x-=lowbit(x);return res;}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&n);fac[0]=1;
	for(ri i=1;i<=n;i++)add(i,1),fac[i]=fac[i-1]*i%mod;
	for(ri i=1;i<=n;i++){
	scanf("%d",&a[i]);
	ans=(ans+1ll*query(a[i]-1)*fac[n-i]%mod)%mod;
	add(a[i],-1);
	}
	printf("%lld
",ans+1);
	return 0;
}