题解P5367【模板】康托展开

VinstaG173 · 2019-05-11 15:16:18 · 题解

前置知识：前缀积&树状数组

树状数组模板

首先我们可以了解，对于第i个位置，若该位置的数是未出现在之前位置上的数中第k大的，那么有(k-1) \times (N-i)!种方案是该位置上比这个排列小的，所以总排名比该排列小。

由此我们可以得到，该排列的排名等于\sum_{i=1}^{N}(rank(a_i)-1) \times (N-i)!。其中rank(a_i)=k表示a_i在未出现在之前位置上的数中是第k大的。

对于阶乘，我们可以用前缀积直接O(N)维护出来。

代码：

fac[0]=1;//注意0!=1
for(int i=1;i<N;++i)
{
    fac[i]=fac[i-1]*i%MOD;
}

对于rank(a_i)，我们怎么做呢？\text{Treap}上一波？

不用那样。无耻地看看算法标签可以发现用树状数组。

最先对每个数add(1)，然后每次删除a_i只要add(-1)即可，sum就是rank。

就是这样：

for(int i=1;i<=N;++i)l[i]=i&-i;
for(int i=1;i<=N;++i)add(i,1);
for(int i=1;i<=N;++i)
{
    scanf(" %d",&a[i]);
    //计算
    add(a[i],-1);
}

然后这道题就愉快地做完了。

完整Code:

#include<cstdio>
#define LL long long
const int MOD=998244353;
int N,a[1000003],c[1000003],l[1000003];
LL fac[1000003],ans;
void add(int x,int k)
{
    while(x<=N)
    {
        c[x]+=k;
        x+=l[x];
    }
}
int sum(int x)
{
    int t=0;
    while(x>0)
    {
        t+=c[x];
        x-=l[x];
    }
    return t;
}
int main()
{
    scanf(" %d",&N);
    fac[0]=1;
    for(int i=1;i<N;++i)
    {
        fac[i]=fac[i-1]*i%MOD;
        l[i]=i&-i;
    }
    l[N]=N&-N;
    for(int i=1;i<=N;++i)add(i,1);
    for(int i=1;i<=N;++i)
    {
        scanf(" %d",&a[i]);
        ans=(ans+((sum(a[i])-1)*fac[N-i])%MOD)%MOD;
        add(a[i],-1);
    }
    printf("%lld\n",ans+1);
    return 0;
}