贪心+计数：CF1612G

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134747631

https://www.luogu.com.cn/problem/CF1612G

贪心考虑如何放最优。

假设当前出现次数最多为 $i$ ，有 $k$ 个这样的数，打表可得左边 $k$ 个随便放，右边 $k$ 个随便放，然后递归下去即可，当前层方案数为 $(k!)^2$ 。

在这个过程中顺便维护最大值即可。

	m=read(); init((int)1e6); 
	mx=0; ans=1; 	
	for(i=1; i<=m; ++i) k=read(), mp[k]++, Add(sum, k); 
	for(i=1e6; i>=2; --i) {
		k=mp[i]; if(!k) continue; 
		Add(sum, -2*k); Mul(ans, Z(fac[k])); 
//		if(k) debug("> [%lld] %lld %lld | %lld | %lld %lld\n", i, k, sum, mx, sum+k, k+k*(i-2)); 
		Add(mx, (k+k*(i-2))%mo*(sum+k)%mo); 
		mp[i-2]+=mp[i]; Mod(mp[i-2]); 
	}
	k=mp[1]; if(k) Mul(ans, fac[k]); 
	printf("%lld %lld\n", mx, ans);