P3477 [POI2008] PER-Permutation 解题报告

· · 题解

可能更好的阅读体验

（upd：对 Hack 的有关分析已更新，见上个人博客↑）

解题思路：

首先看到这道题求排名，感觉还挺像康托展开的，但是康拓展开求的是 不会出现重复元素的排列 的排名，而这道题的难题主要有两个：

可重复和未知模数。

对于可能重复的元素：

我们思考康托展开本身的公式。

对于一个 1 到 n 的排列：{a_1,a_2,a_3,\dots,a_n}，其排名为：

\sum_{i=1}^{n} sum_{a_i}\cdot (n-i)!

而 sum_{a_i} 表示在 a_i 之后比它元素小的个数。

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

那考虑如何去重呢？

我们的 (n-i)! 表示的是 (i+1)-n 位置所有的方案数，对于不重复元素，两个元素互换位置是不同的方案，而重复的元素，两个元素互换位置方案相同，造成了方案数的重复计算。

因此，我们考虑将重复元素提出来，例如 {39,39,39,39}，它是一个方案，却计了 4! 次。

所以，设从 i-n 位置一共有 piece_i 种元素，cnt_{j} 表示在当前的 piece_i 下的第 j 个元素，答案为：

ans=\sum_{i=1}^{n} \dfrac{sum_{a_i}\cdot (n-i)!}{\prod_{j=1}^{piece_{i}} cnt_j}

然后你发现，如果从左往右扫，不断删除元素对于 cnt_j 的处理较难，所以考虑从右往左倒序枚举，这样就成为了加入元素，无论是分子还是分母都较为简单。

对于不明的模数

对于不定模数，或许有两种解决方式：

不知道数据有没有 114514 一类的模数，但是显然 114514 不是质数，所以费马小定理不能使用。

而我们只能考虑扩展欧几里得算法了，它要求我们求解的模数与求解数互质。

所以我们可以对分母 \prod_{j=1}^{piece_{i}} cnt_j 和模数分解质因数，对于模数没有的质因子，扩展欧几里得求逆元。

对于共同的质因子，我们考虑直接消去，因为 ans 是整数，所以 \dfrac{sum_{a_i}\cdot (n-i)!}{\prod_{j=1}^{piece_{i}}\limits cnt_j} cnt_j 是整数，所以若存在共同质因子 p_i，其分子一定存在比分母更多的质因子 p_i，所以直接消去分子和分母所有的 p_i，然后使分子乘上本身比分母多的 p_i 即可。

(tips:有关Hack，请注意这里的分子包含 suma，即帖中的 w。)

使用树状数组优化一下，跑的还是比较快的。

#include<bits/stdc++.h>
#define il inline
#define rg register int
#define cout std::cout
#define cerr std::cerr
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef long double llf;
const ff eps=1e-8;
int Max(int x,int y)    <% return x<y?y:x; %>
int Min(int x,int y)    <% return x<y?x:y; %>
int Abs(int x)  <% return x>0?x:-x; %>
#if ONLINE_JUDGE
char INPUT[1<<20],*p1=INPUT,*p2=INPUT;
#define getchar() (p1==p2 && (p2=(p1=INPUT)+fread(INPUT,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
il int read(){
    char c=getchar();
    int x=0,f=1;
    while(c<48) <% if(c=='-')f=-1;c=getchar(); %>
    while(c>47) x=(x*10)+(c^48),c=getchar();
    return x*f;
}const int maxn=3e5+5;

int n,Mod,ptot,p[maxn],a[maxn],sa[maxn],rank[maxn],len;
int cnt_numerator[maxn],cnt_denominator[maxn];
ll sum[maxn],ans,cnt[maxn];

il ll mymod(ll x){ return x<Mod?x:x-Mod; }

il ll qpow(ll x,int k){
// x^k
    ll res=1;
    while(k){
        if(k&1) res=res*x%Mod;
        x=x*x%Mod;
        k=k>>1;
    }
    return res;
}

il void exgcd(int a,int b,int &x,int &y){
// 求得x是a在模Mod意义下的乘法逆元
    if(!b)  return x=1,y=0,void();
    exgcd(b,a%b,y,x);y=(y-(a/b)*x%Mod+Mod)%Mod;
}

#define lowbit(x) (x&-x)
il ll query(int pos){
    ll res=0;
    while(pos){
        res+=sum[pos];
        pos-=lowbit(pos);
    }
    return res;
}
il void update(int pos,int val){
    while(pos<=len){
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}
#undef lowbit

il ll solve_numerator(ll numerator){
// 对分子分解质因数
    if(!numerator)  return 1;
    for(rg i=1;i<=ptot;++i){
        if(numerator%p[i])  continue;
        while(!(numerator%p[i]))  ++cnt_numerator[i],numerator/=p[i];
    }
    return numerator;
}

il void back(ll numerator){
// 撤回ssum对cnt_numerator的影响
    if(!numerator)  return;
    for(rg i=1;i<=ptot;++i){
        if(numerator%p[i])  continue;
        while(!(numerator%p[i]))  --cnt_numerator[i],numerator/=p[i];
    }
}

il ll solve_denominator(ll denominator){
// 对分母分解质因数
    if(!denominator)    return 1;
    for(rg i=1;i<=ptot;++i){
        if(denominator%p[i])    continue;
        while(!(denominator%p[i]))    ++cnt_denominator[i],denominator/=p[i];
    }
    return denominator;
}

il void work(){
    int numerator=1,denominator=1,res=1,x=0,y=0,save;
    for(rg i=n;i>=1;--i){
        res=1;
        ++cnt[a[i]];
        numerator=numerator*solve_numerator(n-i)%Mod;
        save=numerator;
        denominator=denominator*solve_denominator(cnt[a[i]])%Mod;
        update(rank[i],1);
        int ssum=query(rank[i]-1);
        if(!ssum)   continue;   // 没有比当前位小的直接continue
        numerator=numerator*solve_numerator(ssum)%Mod;
        exgcd(denominator,Mod,x,y);     // 求非共同质因子的逆元x
        x=mymod(x%Mod+Mod);
        for(rg j=1;j<=ptot;++j) res=res*qpow(p[j],cnt_numerator[j]-cnt_denominator[j])%Mod; // 消去共同质因子
        res=res*numerator%Mod*x%Mod;
        ans=mymod(ans+res);
        back(ssum);numerator=save;
    }
}

il void input(){
    n=read(),Mod=read();
    for(rg i=1;i<=n;++i)    a[i]=read(),sa[i]=rank[i]=a[i];
    std::sort(sa+1,sa+1+n);
    len=std::unique(sa+1,sa+1+n)-(sa+1);
    for(rg i=1;i<=n;++i)    rank[i]=std::lower_bound(sa+1,sa+1+len,rank[i])-sa; // 离散化
    int save=Mod;
    for(rg i=2;i<=sqrt(Mod);++i){
        if(Mod%i)   continue;
        p[++ptot]=i;
        while(!(Mod%i))   Mod/=i;
    }
    if(Mod^1)   p[++ptot]=Mod;
    Mod=save;
}

signed main(){
#ifndef ONLINE_JUDGE
freopen("PER.in","r",stdin);
#endif
    input();
    work();
    printf("%lld\n",mymod(ans+1));
    return 0;
}