本文共 996 字，大约阅读时间需要 3 分钟。

题目描述

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

输入格式

第一行一个正整数NN。

第二行NN个正整数，表示1\sim N1∼N的一种全排列。

输出格式

一行一个非负整数，表示答案对998244353998244353取模的值。

输入输出样例

输入 #1 复制 3 2 1 3 输出 #1 复制 3 输入 #2 复制 4 1 2 4 3 输出 #2 复制 2 说明/提示 对于10%10%数据，1\le N\le 101≤N≤10。

对于50%50%数据，1\le N\le 50001≤N≤5000。

对于100%100%数据，1\le N\le 10000001≤N≤1000000。

思路：用树状数组+康托展开(百度)

#include 
   
    typedef long long ll;const ll mod = 998244353;ll a[1000005];ll b[1000005];ll c[1000005];int n;void init(int n){//pretreatment	b[0] = 1; 	for(int i = 1;i <= n;i++){		b[i] = (b[i-1]*i)%mod;	}	return;}void update(int x,int k){	for(int i = x;i <= n;i += i&-i){		c[i] += k;	}}ll query(int x){	ll ans = 0;	for(int i = x;i > 0;i -= i&-i){		ans += c[i];	}	return ans;}int main(){	ll ans = 0; 	scanf("%d",&n);	init(n);	for(int i = 1;i <= n;i++){		scanf("%lld",a+i);		update(i,1);	}	for(int i = 1;i <= n;i++){		ll t = query(a[i])-1;//减去自己本身		ans = (ans+(t*b[n-i])%mod+mod)%mod;		update(a[i],-1);	}	printf("%lld\n",ans+1);	return 0;}
   

转载地址：http://piqp.baihongyu.com/