BZOJ5322 JXOI2018排序问题

　　对于一个序列，重排后有序的概率显然是∏cnt_i!/n!，其中cnt_i为第i种数出现次数。要使概率最小，显然应该让各种数字尽量平均分配。剩下的是div2BC左右的大讨论。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
#define M 10000010
#define P 998244353
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int T,n,m,l,r,a[N],cnt[N],fac[N+M];
int ksm(int a,int k)
{
    int s=1;
    for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
    return s;
}
int inv(int a){return ksm(a,P-2);}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj5322.in","r",stdin);
    freopen("bzoj5322.out","w",stdout);
    const char LL[]="%I64d
";
#else
    const char LL[]="%lld
";
#endif
    T=read();
    fac[0]=1;for (int i=1;i<N+M;i++) fac[i]=1ll*fac[i-1]*i%P;
    while (T--)
    {
        n=read(),m=read(),l=read(),r=read();int u=n,v=m;
        for (int i=1;i<=n;i++) a[i]=read();
        sort(a+1,a+n+1);
        int tot=0;
        for (int i=1;i<=n;i++)
        {
            int t=i;
            while (t<n&&a[t+1]==a[i]) t++;
            cnt[++tot]=t-i+1;i=t;
        }
        unique(a+1,a+n+1);n=tot;
        int L=n+1,R=0;
        for (int i=n;i>=1;i--) if (l<=a[i]) L=i;else break;
        for (int i=1;i<=n;i++) if (r>=a[i]) R=i;else break;
        int ans=1;
        for (int i=1;i<=L-1;i++) ans=1ll*ans*fac[cnt[i]]%P;
        for (int i=R+1;i<=n;i++) ans=1ll*ans*fac[cnt[i]]%P;
        for (int i=L;i<=R;i++) cnt[i-L+1]=cnt[i];
        n=R-L+1;sort(cnt+1,cnt+n+1);tot=r-l+1-n;cnt[++n]=P;
        for (int i=1;i<=n;i++)
        if (m>=1ll*tot*(cnt[i]-cnt[i-1])) m-=tot*(cnt[i]-cnt[i-1]),tot++;
        else
        {
            ans=1ll*ans*ksm(fac[cnt[i-1]+m/tot],tot)%P*ksm(cnt[i-1]+m/tot+1,m%tot)%P,m=0;
            for (int j=i;j<n;j++) ans=1ll*ans*fac[cnt[j]]%P;
            break;
        }
        ans=1ll*fac[u+v]*inv(ans)%P;
        printf("%d
",ans);
    }
    return 0;
}