康托展开

· · 个人记录

求一个全排列的排名。

公式

ans=1+\sum_{i=1}^na_i\times(n-i)!

代码

需要用到树状数组。

ll c[N],ji[N];
void add(int x,int v){
    for(;x<=n;x+=x&-x)
        c[x]+=v;
}
ll ask(int x){
    ll ans=0;
    for(;x;x-=x&-x)
        ans+=c[x];
    return ans;
}
ll Cantor(int n,int *a,ll mod){
    ll ans=0;
    //mod=998244353;
    ji[0]=1;
    for(int i=1;i<=n;i++)
        ji[i]=ji[i-1]*i%mod,c[i]=0;
    for(int i=1;i<=n;i++){
        ans=(ans+ask(a[i]-1)%mod*ji[i-1]%mod)%mod;
        add(a[i],1);
    }
    return ans+1;
}