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

· · 题解

这是一道挺水的题

虽然我做了七次

好了好了，不废话了。

对于康托展开，先贴公式，方便对后面的代码进行理解：

就是\huge{a}\small{i}在n个数里第几大去乘（n-i）的阶乘，然后一直加到\huge{a}\small{n}。 在整个程序里，最难的是如何方便、快速的求出\huge{a}\small{i}在n个数里是第几大。

首先，暴力肯定行不通，肯定会 TLE ，因此，可以在康托展开的阶乘预处理时同时与处理好，他是第几大的。

接着，还有一个很严重的问题：用普通的数组肯定会炸，因此要用树状数组。

我解释的差不多了，剩下的一些小细节会在代码里注释出来：

#include<bits/stdc++.h>
using namespace std;
long long C[1000005],fact[1000005],n;
long long lowbit(long long x)
{
    return x&(-x);
}
void add(long long x,long long y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        C[i]+=y;
}
long long getsum(long long x)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans+=C[i];
    return ans;
}
int main()
{
    long long i,can=0;
    cin>>n;
    fact[0]=1;
    for(i=1;i<=n;i++)
    {
        fact[i]=fact[i-1]*i%998244353;//方便康托展开
        add(i,1);//预处理，存入树状数组C[i]中
    }
    for (i=1; i<=n; i++)
    {
        int x;
        scanf("%d",&x);
        can=(can+(getsum(x)-1)*fact[n-i])%998244353;//无时无刻模它，因为随时它都可能会超出long long的数据范围
        add(x,-1);//由于这个数用过了，所以要减1
    }
    cout<<can+1<<endl;//记得加1，因为算出的是这个全排列前面还有几个全排列
    return 0;
}

温馨提示：

没学好树状数组的话，
不推荐来做这题。

另外，感谢@Randolph、的思路