luogu-P5367 康托展开【模板】

题目描述

求

输入格式

第一行一个正整数

第二行

输出格式

一行一个非负整数，表示答案对

输入输出样例

输入 #1

3
2 1 3

输出 #1

输入 #2

4
1 2 4 3

输出 #2

说明/提示

对于 $10\%10%数据，1le Nle 101≤N≤10。$

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

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

$康拓展开其实就是给一个排列，要你求出这个排列在全排列中的位置。$

$经常可以起到哈希表的作用$

$我们用3 4 2 1 5 来举个栗子$

$先看3 显然第一位可以是1,2，所以ans+=2*4！（4！指的是当第一位确定时后面4位的排列数）$

$再看第二位4 当第一位3已经确定时，第二位排在4前面的只有1,2 所以ans+=2*3!（即4后面比其小的数有两个）$

$第三位2，前两位确定时第三位排在2前面的只有一个$

$所以康托展开的公式为 ans=Σki*(n-i)! （ki为当前位后面比当前数小的数的个数）$

$此处要求ki的话如果暴力跑一遍需要的时间复杂度为 O(N²) 所以我们可以在线维护一个树状数组记录当前位前面有几个数比其小，所以时间复杂度可以简化为O(NlbN)$

$*下次遇到在线求比当前数小的数的个数可以用树状数组解决，但前提条件一定是在线！！！树状数组不可离线操作！！！$

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=1000005;
 5 const int MOD=998244353;
 6 LL n,a[MAX],c[MAX],ans;
 7 LL mul[MAX];
 8 void add(LL x,LL y){for (;x<MAX;c[x]=(c[x]+y)%MOD,x+=(x&-x));}
 9 LL search(LL x){LL an=0;for (;x>0;an=(an+c[x])%MOD,x-=(x&-x));return an;}
10 int main(){
11     freopen ("cantor.in","r",stdin);
12     freopen ("cantor.out","w",stdout);
13     LL i,j,zt;
14     scanf("%lld",&n);
15     memset(c,0,sizeof(c));
16     mul[0]=1;
17     for (i=1;i<=n;i++){
18         scanf("%lld",a+i);
19         mul[i]=(mul[i-1]*i)%MOD;
20     }
21     ans=1;
22     for (i=1;i<=n;i++){
23         zt=a[i]-1-search(a[i]);
24         add(a[i],1);
25         ans=(ans+zt*mul[n-i])%MOD;
26     }
27     printf("%lld",ans);
28     return 0;
29 }