校内省选比赛D3

鶸啊(✺ω✺)
今天考的是江西去年省选题，据说他们只有一试，80分就B类进队了。我上午打了110分，但sb错误不断又挂成70了……认真点吧，如果这就是省选，你又找谁哭呢？谁管你打挂没。

sort

• 50分挺水吧……写一下样例，找到规律。假如你添加数之后，有$k$k个本质不同的数，每个数出现的次数为$s[i]$s[i]，那么答案就是$(n+m)!\Pi_{i=1}^{k}\frac{1}{s[i]!}$(n+m)!Πi=1k​s[i]!1​。容易发现，我们只要保证每次添加的数是出现次数最少的就一定最优。那么，写一个二叉堆，每次找出出现次数最小的点，把他的$sum$sum++，最后求一下答案就好了。
• 100分呢？注意到虽然$a_i$ai​和$l,r$l,r很大，但是$n$n不大。而我们添加的次数正好与$n$n有关。这里为什么说与$n$n有关？
• 我们知道了每次把次数最少的次数+1，其实没有必要一次一次加，如果按照当前出现次数排序之后，你画一个类似条形统计图的东西，其实就是找一个高峰，然后把前面所有柱子变成和它一样高。如果能做到，继续；否则，尽量保持前面柱子一样高地去增加次数。
• 这个模拟处理，妙在快速的求把前面柱子填满需要多少次。
• 一、对原始a进行排序，求出每一个数出现次数，把不属于$[l,r]$[l,r]内的数剔除并直接把贡献乘到答案里。
• 二、按照出现次数排序，把出现次数相同的数合并为一个类，并记录这个类由多少个数组成。
• 三、$f$f表示当前柱子高度为$a[i-1]$a[i−1]的数有多少个，开始递推。如果填满到$a[i]$a[i]高度代价超过此时剩余次数，计算答案，调出循环；否则，所有柱子填满，减去代价，继续操作。
• 注意：分析好数据范围，合理开数组。不然像我这样的就GG了。

Coding

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=12e6+100;
const int mod=998244353;
int t,n,m,l,r,f,cnt,tot,ans,a[N],b[N],jie[N];
int power(int a,int b){
	int res=1%mod;
	for(;b;b>>=1){
		if(b&1) res=1LL*res*a%mod;
		a=1LL*a*a%mod;
	}
	return res;
}
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	jie[0]=1;
	for(int i=1;i<=2e5;++i) jie[i]=1LL*jie[i-1]*i%mod;
	scanf("%d",&t);
	while(t--){
		f=cnt=tot=0;ans=1;
		scanf("%d%d%d%d",&n,&m,&l,&r);
		for(int i=1;i<=n;++i) scanf("%d",&a[i]);
		sort(a+1,a+n+1);f=r-l+1;
		for(int i=1,j=1;i<=n;i=j){
			while(a[i]==a[j]&&j<=n) j++;
			if(a[i]<l||a[i]>r) ans=1LL*ans*jie[j-i]%mod;
			else b[++tot]=j-i,f-=1;
		}
		sort(b+1,b+tot+1);
		for(int i=1,j=1;i<=tot;i=j){
			while(b[i]==b[j]&&j<=tot) j++;
			a[++cnt]=b[i],b[cnt]=j-i;
		}
		a[++cnt]=1e9;b[cnt]=1;
		for(int i=1,M=m;i<=cnt;++i){
			int s=a[i]-a[i-1];
			ll val=1LL*s*f;
			if(val>M){
				int t=a[i-1]+M/f;int num=M%f;
				ans=1LL*ans*power(jie[t],f-num)%mod;
				ans=1LL*ans*power(jie[t+1],num)%mod;
				for(int j=i;j<cnt;++j) ans=1LL*ans*power(jie[a[j]],b[j])%mod;
				break;
			}else M-=val,f+=b[i];
		}
		ans=1LL*jie[n+m]*power(ans,mod-2)%mod;
		printf("%d\n",ans);
	}
	return 0;
} 

game

• 看懂题目之后，显然可以$n!$n!枚举变成僵尸的顺序，$n^2$n2暴力判断轮数，计算平均数即可。
• $l=1$l=1，发现$1$1在哪个位置，就是几轮。可以直接求1在每一位对答案的贡献。
• 结合，期望得分30。（某人因为分值数据，写错变量名少了10分）。

guard

• 显然，我们可以先预处理一下，亭子$i$i能向左看到多少个亭子。只需要维护一个斜率，如果当前斜率大于上次斜率，就看不到。否则继续。
• $2^n$2n枚举使用保镖情况，此时右端点确定，枚举每一个$l$l，判断区间是否被覆盖完全，更新答案。
• 这样保证了复杂度是$2^n*n$2n∗n，稳妥的30分。
• （某人因为斜率初始值1e7不够大，爆零了）。