[JXOI2018]排序问题

2021-06-06 12:05

阅读：298

标签：固定 www tps ace main clear i++ ack com

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
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;
vectorv;
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=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

[JXOI2018]排序问题

标签：固定 www tps ace main clear i++ ack com

原文地址：https://www.cnblogs.com/Troverld/p/14611004.html

上一篇：用基础Array数组实现动态数组、链表、栈和队列

下一篇：Spring扩展———自定义bean组件注解

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[JXOI2018]排序问题
文章链接：http://soscw.com/essay/91276.html

亲，登录后才可以留言！

[JXOI2018]排序问题

XIV.[JXOI2018]排序问题

评论

热门文章

推荐文章

最新文章

置顶文章