2021.08.05 P5357 康托展开模板（康托展开）

2021.08.05 P5357 康托展开模板（康托展开）

P5367 【模板】康托展开 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.康托展开

算法学习笔记(56): 康托展开 - 知乎 (zhihu.com)

题意：

求 1∼N 的一个给定全排列在所有1∼N 全排列中的排名。结果对 998244353取模。

分析：

如题。

代码如下：

树状数组优化，时间复杂度O(nlogn)

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=1e6+10;

const ll mod=998244353;

int n,a[N],tree[N];

ll ans,A[N],fact[N];

inline ll read(){

	ll s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int lowbit(int x){

	return x&-x;

}

void add(int x,int k){

	for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;

}

int query(int x){

	int fin=0;

	for(int i=x;i;i-=lowbit(i))fin+=tree[i];

	return fin;

}

int main(){

	n=read();

	fact[1]=1;

	for(int i=2;i<n;i++)fact[i]=fact[i-1]*i%mod;

	//for(int i=1;i<n;i++)cout<<fact[i]<<" ";cout<<endl<<endl;

	for(int i=1;i<=n;i++)a[i]=read();

	for(int i=n;i>=1;i--){

		A[i]=query(a[i]);

		add(a[i],1);

	}

	//for(int i=1;i<=n;i++)cout<<A[i]<<" ";cout<<endl<<endl;

	for(int i=1;i<n;i++)ans=(ans+A[i]*fact[n-i]%mod)%mod;

	cout<<(ans+1)%mod;

	return 0;

}

2021.08.05 P5357 康托展开模板（康托展开）的相关教程结束。