我们的生活充满了未知与玄学
----------------------------------------
链接：P5367
----------------------------------------
康拓展开在此题就是求一个全排列的排名。
我觉得它适合用来优化内存，这样存全排列虽然还要展开，但是内存小啊。
----------------------------------------
康拓展开的原理
----------------------------------------
首先，我们要求出阶乘，不然会TLE，
然后根据公式计算就可以了。
‘但是我们怎么知道对于每一个数，他是当前没有用过的数的排名呢？
我们可以用一个树状数组来维护，每使用一个，就在相应下标下-1。
询问时用树状数组求出的区间和就是排名了
------------------------------------------
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int t[1000001]; 5 int n; 6 int mod=998244353; 7 long long f[1000001]; 8 int lowbit(int x){ 9 return x & -x; 10 } 11 void add(int x,int p){ 12 while(p<=n){ 13 t[p]+=x; 14 p+=lowbit(p); 15 } 16 return ; 17 } 18 int sum(int x){ 19 int ans=0; 20 while(x){ 21 ans+=t[x]; 22 x-=lowbit(x); 23 } 24 return ans; 25 } 26 int now; 27 long long anss; 28 int main(){ 29 f[0]=1; 30 scanf("%d",&n); 31 for(int i=1;i<=n;++i) 32 f[i]=f[i-1]*i%mod; 33 for(int i=1;i<=n;++i) 34 add(1,i); 35 for(int i=n;i>=1;i--){ 36 scanf("%d",&now); 37 anss+=(((sum(now)-1)*f[i-1])%mod)%mod; 38 anss%=mod; 39 add(-1,now); 40 } 41 printf("%lld\n",anss+1); 42 return 0; 43 }
原文：https://www.cnblogs.com/For-Miku/p/11351469.html
