题解 P5367 【【模板】康托展开】

大水题

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000005],n;
int num[1000005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        num[i]=i;
    }
    int ans=1;
    do{
        bool flag=1; 
        for(int i=1;i<=n;i++){//判断相等 
            if(a[i]!=num[i]){
                flag=0;
                break;
            }
        }
        if(flag){
            printf("%d",ans);//相等就输出 
            return 0;
        }
        ans++;
    }while(next_permutation(num+1,num+1+n));//暴力枚举全排列 
    return 0;
}

这人疯了不要搭理他

咳咳，以上这种粗鲁蛮横的做法肯定是AC不了的，众所周知，这题我们要用一个神奇的方法——康托展开！

康托展开讲的是什么故事呢？是这样的：对于一个1到n的排列\{a_1,a_2,\cdots,a_n\}，比它小的排列有这些个：

\sum^n_{i=1}sum_{a_i}\times (n-i)!

而sum_{a_i}，就是在a_i后面的元素里比它小的元素个数，即\sum_{j=i}^n(a_j<a_i)

是不是大家开始一脸懵了呢？没关系，这是正常现象，因为上面那两句压根不是给人看的，咱们还是从一个具体的栗子讲起：

2,4,1,5,3

看这个排列，怎样求他是第几小的呢？别急，咱们一位一位去考虑！

• 第一位是2，比它小的就只有一个1了，所以只有1放在这一位，才会比它小，那后面的呢？你爱怎么排怎么排！后面有4个数，所以一共有4!种排列方法，也就是说一共有1\times4!种方法
• 第二位是4，比它小的有1,2,3，但是2已经在前面固定了，所以能放在这一位的就只有1,3这2个数，而后面呢，有3个数，就有3!种排列方法，所以一共有2\times3!种方法
• 第三位的1没有更小的啦，所以一共是0\times2!种方法
• 第四位在5后面有比5小的3，一共1个数，1\times1!种方法
• 第五位其实压根都不用考虑了，反正都用过了，要考虑的话也是0\times0!种方法
• 最后我们再把每一位的加起来：1\times4!+2\times3!+0\times2!+1\times1!+0\times0!=36种，所以排名是第37名

经过这么一通解释，现在大家应该都理解了康托展开的原理，上面的鬼畜柿子也应该懂了吧！那接下来就应该考虑代码实现的问题啦！

首先，阶乘这一块是珂以直接预处理出来的：

    for(int i=1;i<=n;i++)
    jc[i]=(jc[i-1]*i)%998244353;//阶乘的定义

然后，根据定义算出排名：

    int ans=0;
    for(int i=1;i<=n;i++){
      int sum=0;
      for(int j=i;j<=n;j++)
        if(a[i]<a[j])sum++;//统计sum
     ans=(ans+sum*jc[n-i])%998244353;//计算ans                       
    }
    printf("%d",ans+1);//别忘了+1

这么写的，你是不是又想TLE了？？？

好吧，以上代码没问题，但是这个题的数据很友（du）善（liu），O(n^2)的复杂度是跑不过的......那要多少呢？O(\log n)差不多，带\log的就那几样数据结构，经过精挑细选，我们就用常数小，操作方便，代码又好写的树状数组吧！

能优化的，无非就是 统计sum 的那一步......等会，树状数组是干啥用的来着？

单点修改，区间查询

那我们就要把sum的计算转化成区间和，这里有一个方法：一开始每个数都是1，如果某个数出现过了，就把它变成0，而最后要求的sum_{a_i}，就是1到a_i-1的区间和！（为什么？因为比它小的数都在它前面嘛）

咱们还是以刚才2,4,1,5,3的那个栗子来解释：

• 一开始，树状数组每个元素的值是1,1,1,1,1
• 算到2的时候，sum=1，树状数组每个元素的值是1,0,1,1,1
• 算到4的时候，sum=1+0+1=2，树状数组每个元素的值是1,0,1,0,1
• 算到1的时候，sum=0，树状数组每个元素的值是0,0,1,0,1
• 算到5的时候，sum=0+0+1+0=1，树状数组每个元素的值是0,0,1,0,0
• 算到3的时候，sum=0+0=0，树状数组每个元素的值是0,0,0,0,0

最后，就是写代码的时间啦！

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;//虽然不知道这题不开long long会不会见祖宗，但保险起见还是开一下吧
ll tree[1000005];//树状数组
int n;
  //树状数组的“老三件”：lowbit，修改，求和
int lowbit(int x){
    return x&-x;
}
void update(int x,int y){
    while(x<=n){
        tree[x]+=y;
        x+=lowbit(x);   
    }
}
ll query(int x){
    ll sum=0;
    while(x){
        sum+=tree[x];
        x-=lowbit(x);   
    }
    return sum;
}
const ll wyx=998244353;//懒人专用
ll jc[1000005]={1,1};//存阶乘的数组
int a[1000005];//存数的
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){//预处理阶乘数组和树状数组
        jc[i]=(jc[i-1]*i)%wyx;
        update(i,1);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ans=(ans+((query(a[i])-1)*jc[n-i])%wyx)%wyx;//计算ans
        update(a[i],-1);//把a[i]变成0（原来是1，减1不就是0嘛）
    }
    printf("%lld",ans+1);//别忘了+1
   return /*2333333333*/ 0;
}

总结一下：

• 我们今天学到了一个新技能：康托展开，
• 它是用来解决排列的问题的
• 它的公式是这个：ans=\sum^n_{i=1}sum_{a_i}\times (n-i)!
• 必要时可以用树状数组优化计算sum的过程
• 据说以后这玩意还可以用来弄哈希啥的，这里我刚学，就不说了
• The end