BZOJ5322 [Jxoi2018]排序问题【贪心】

题目链接

题解

意思就是使有序的排列尽量少

就是使相同的数尽量少

然后大力贪心即可

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define REP(i,n) for (register int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define res register

using namespace std;

const int maxn = 200005,maxm = 10200005,INF = 1000000000,P = 998244353;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int n,m,l,r,a[maxn];

int fac[maxm];

inline int qpow(int a,int b){

	int ans = 1;

	for (; b; b >>= 1,a = 1ll * a * a % P)

		if (b & 1) ans = 1ll * ans * a % P;

	return ans;

}

void init(){

	fac[0] = 1;

	for (res int i = 1; i < maxm; i++)

		fac[i] = 1ll * fac[i - 1] * i % P;

}

int bac[maxm],tail;

int main(){

	init();

	int T = read(),ans;

	while (T--){

		n = read(); m = read(); l = read(); r = read(); ans = fac[n + m];

		REP(i,n) a[i] = read();

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

		tail = 0; int cnt = 0,M = 0;

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

			if (i != 1 && a[i] != a[i - 1]){

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

					bac[cnt]++,tail++,M = max(M,cnt);

				}

				else ans = 1ll * ans * qpow(fac[cnt],P - 2) % P;

				cnt = 1;

			}

			else cnt++;

		}

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

			bac[cnt]++,tail++,M = max(M,cnt);

		}

		else ans = 1ll * ans * qpow(fac[cnt],P - 2) % P;

		bac[0] += r - l + 1 - tail;

		for (res int i = 0; m; i++,M = max(M,i)){

			if (M == i){

				int tot = m / bac[i],lef = m - tot * bac[i];

				ans = 1ll * ans * qpow(qpow(fac[i + tot],P - 2),bac[i] - lef) % P;

				ans = 1ll * ans * qpow(qpow(fac[i + tot + 1],P - 2),lef) % P;

				bac[i] = M = 0;

				break;

			}

			if (bac[i] >= m){

				bac[i + 1] += m;

				bac[i] -= m;

				m = 0;

			}

			else {

				m -= bac[i];

				bac[i + 1] += bac[i];

				bac[i] = 0;

			}

		}

		for (res int i = 0; i <= M; i++){

			ans = 1ll * ans * qpow(qpow(fac[i],P - 2),bac[i]) % P;

			bac[i] = 0;

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

BZOJ5322 [Jxoi2018]排序问题【贪心】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ5322 [Jxoi2018]排序问题 【贪心】

题目链接

题解

最新文章

热门文章

BZOJ5322 [Jxoi2018]排序问题【贪心】