XIV.[JXOI2018]排序问题

本题好像又不算期望罢……

根据一些简单的推理，我们发现最终答案就是

\[\dfrac{(n+m)!}{\prod\limits_{i}cnt_i!} \]

其中\(cnt_i\)表示有多少个数是\(i\)。（这很简单，因为只有每个位置一一对应才能排序成功；但是值相同的数之间两两可以相互替换，故要除掉）

我们发现，对于\(i\notin[l,r]\)，这个\(cnt_i\)就已经固定了，可以直接通过哈希表/离散化预处理出来；而对于\(i\in[l,r]\)，\(cnt_i\)并不固定，而我们希望它尽量平均，故我们先用这\(m\)个位置尽量补，补到对于\(i\in[l,r]\)，\(cnt_i\)全部相等，然后剩下的直接平均分即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=10200000;
int T,n,m,l,r,a[200100],b[200100],c[200100],fac[10200100],inv[10200100],res;
vector<int>v;
int ksm(int x,int y){
	int z=1;
	for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
	return z;
}
int main(){
	fac[0]=1;for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
	inv[N]=ksm(fac[N],mod-2);for(int i=N-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d",&n,&m,&l,&r),res=fac[n+m],v.clear();
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
		sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
		for(int i=1;i<=n;i++)b[lower_bound(v.begin(),v.end(),a[i])-v.begin()]++;
		c[0]=r-l+1;
		for(int i=0;i<v.size();b[i++]=0)if(l<=v[i]&&v[i]<=r)c[0]--,c[b[i]]++;else res=1ll*res*inv[b[i]]%mod;
		int lim=0;
		for(lim=0;c[lim]!=r-l+1;lim++){
			if(c[lim]<=m)m-=c[lim],c[lim+1]+=c[lim],c[lim]=0;
			else{c[lim+1]+=m,c[lim]-=m,m=0;break;}
		}
		if(c[lim]==r-l+1){
			int tmp=m%c[lim],now=m/c[lim];
			res=1ll*res*ksm(inv[lim+now+1],tmp)%mod*ksm(inv[lim+now],c[lim]-tmp)%mod;
		}else for(int i=lim,j=0;j!=r-l+1;i++)res=1ll*res*ksm(inv[i],c[i])%mod,j+=c[i];
		for(int i=0;i<=n;i++)c[i]=0;
		printf("%d\n",res);
	}
	return 0;
}