「JXOI 2018」排序问题

题目链接

戳我

\(Solution\)

\(50\ pts\)

我们来看一下题目,可以很容易的写出来答案的式子:

\[\frac{(n+m)!}{a_1!a_2!...a_{tot}!}
\]

\(a_1,a_2,...,a_{tot}\)为\(n+m\)个数中不同的数出现的个数

那么\(50\)便很好想了.

我们现在要求的是期望轮数最多,所以\({a_1!a_2!...a_{tot}!}\)要尽量小

所以我们可以贪心求解,每次找出\([l,r]\)中出现次数最少的数,找\(m\)次即可,这用个堆维护一下就好了

\(100 \ pts\)

我们还是需要\({a_1!a_2!...a_{tot}!}\)尽量小

于是我们可以二分出\(a_1,a_2,...,a_{tot}\)中的最小值的最大值，我们令这个值为\(ans\)

那么我们现在就可以知道了\(a_1,a_2,...,a_{tot}\)的分布

对于\(>ans\)的或不在[l,r]这个区间内的,直接将他们阶乘乘起来即可.

对于[l,r]内个数\(<=ans\)的,进行如下操作:

算出将[l,r]内个数\(<=ans\)的边成\(ans\)后剩下\(m\)个数还剩下几个.我们令这个数为\(c\),[l,r]内去见个数\(<=ans\)的数有\(k\)个

我们将这\(c\)个数分成不同的\(c\)个插入数列即可.

所以现在的个数为:

\(c\) 个个数为 \(ans+1\)

\(k-c\)个个数为 \(ans\)

直接快速幂求,最后吧求的乘起来,用\((n+m)!\)除他就好了.

\(Code\)

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

const int mod=998244353;

inline int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

int n,m,tot,a[2000010],sum[2000010];

inline int check(int x,int len){

    int ans=0,flag=0;

    for(int i=1;i<=tot;i++){

        if(sum[i]>x)

            break;

        ans+=sum[i],flag=i;

    }

    int k=(len-tot+flag);

    return m-(k*x-ans);

}

inline int ksm(int a,int b){

    int ans=1;

    while(b){

        if(b&1)

            ans=ans*a%mod;

        a=a*a%mod,b>>=1;

    }

    return ans;

}

int jc[20000010];

main(){

    int T=read(),l,r;

    jc[0]=1;

    for(int i=1;i<=10200000;i++)

        jc[i]=jc[i-1]*i%mod;

    while(T--){

        n=read(),m=read(),l=read(),r=read(),tot=0;

        for(int i=1;i<=n;i++)

            a[i]=read();

        sort(a+1,a+1+n);

        int p=0,js=1;

        a[n+1]=-2147483647;

        for(int i=1;i<=n+1;i++){

            if(a[i]!=a[i+1]){

                if(a[i]<=r&&a[i]>=l)

                    sum[++tot]=i-p;

                else js=js*jc[(i-p)]%mod;

            p=i;

            }

        }

        sort(sum+1,sum+1+tot);

        int L=0,R=m+n,maxx=0;

        while(L<=R){

            int mid=(L+R)>>1;

            if(check(mid,(r-l+1))>=0)

                L=mid+1,maxx=max(maxx,mid);

            else R=mid-1;

        }

        int ans=0,flag=0,len=(r-l+1);

        for(int i=1;i<=tot;i++) {

            if(sum[i]>maxx) break;

            ans+=sum[i],flag=i;

        }

        int k=(len-tot+flag),c=m-(k*maxx-ans);

        for(int i=flag+1;i<=tot;i++) js=js*jc[sum[i]]%mod;

        js=js*ksm(jc[maxx+1],c)%mod,js=js*ksm(jc[maxx],k-c)%mod;

        printf("%lld\n",jc[n+m]*ksm(js,mod-2)%mod);

    }

    return 0;

}

巴特西

「JXOI 2018」排序问题

题目链接

\(Solution\)

\(50\ pts\)

\(100 \ pts\)

\(Code\)

最新文章

热门文章

巴特西

「JXOI 2018」 排序问题

题目链接

\(Solution\)

\(50\ pts\)

\(100 \ pts\)

\(Code\)

最新文章

热门文章

「JXOI 2018」排序问题