P3477 [POI2008] PER-Permutation 解题报告

[POI2008] PER-Permutation

题目描述

Multiset is a mathematical object similar to a set, but each member of a multiset may have more than one membership.

Just as with any set, the members of a multiset can be ordered in many ways. We call each such ordering a permutation of the multiset. For example, among the permutations of the multiset{1,1,2,3,3,3,7,8}. there are {2,3,1,3,3,7,1,8} and{8,7,3,3,3,2,1,1}.

We will say that one permutation of a given multiset is smaller (in lexicographic order) than another permutation, if on the first position that does not match the first permutation has a smaller element than the other one. All permutations of a given multiset can be numbered (starting from one) in an increasing order.

Task Write a programme that reads the description of a permutation of a multiset and a positive integerm from the standard input, determines the remainder of the rank of that permutation in the lexicographic ordering modulo m, writes out the result to the standard output.

多重集合是数学中的一个概念，它的定义很像集合，但是在多重集之中，同一个元素可以出现多次。

和集合一样，多重集的的元素可以有很多种元素的排布顺序。我们把它叫作多重集的排列。

现在我们定义多重集的某个排列\(s_i\)比某个排列\(s_j\)

的大小比较为字典序比较。这样某个多重集的排列可以从小到大得排起来。

现在给你一个元素个数为n的多重集的一个排列和m，求这个排列的排名取模m。

输入格式

The first line of the standard input holds two integers n(\(1\le n \le 300000\)) and m (\(2 \le m \le 10^9\) ) ,separated by a single space. These denote, respectively, the cardinality of the multiset and \dots\ the number m.

The second line of the standard input contains n positive integers \(a_i\)(\(1\le a_i \le 300000\)), separated by single spaces and denoting successive elements of the multiset permutation.

第一行 两个整数n,m

第二行 n个数，代表多重集的排列

输出格式

The first and only line of the standard output is to hold one integer, the remainder modulo m of the rank of the input permutation in the lexicographic ordering.

一行一个整数 排名取模m

样例 #1

样例输入 #1

4 1000
2 1 10 2

样例输出 #1

5

提示

感谢@远航之曲 贡献的翻译

#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;
}