Jury Meeting(思维/数论)

本文主要是介绍Jury Meeting(思维/数论)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目
题意：给定 n n n个人，每人手上有 a i a_i ai​个任务。给定一个排列顺序后，每个人轮流讲自己的任务，每次讲一个。当没有任务时，则轮空。问有多少种排列方式，使得不会出现某个人会连续讲任务的情况。
比如 a = { 1 , 2 } a=\{1,2\} a={1,2}，对于排列 { 1 , 2 } \{1,2\} {1,2}，会出现第二个人连续讲自己的任务的情况；而对于排列 { 2 , 1 } \{2,1\} {2,1}，则不会出现这种情况。
参考
思路：可以发现，会出现连续讲两次的人选，一定是手头任务最多的人。其次，当手头任务最多的人数有2人以上时，不会出现连续讲两次的人选，比如对于数组 { 3 , 3 , 3 } \{3,3,3\} {3,3,3}，这三个人无论怎么排列，起得作用都一样，讲完后都会有相应的人选来轮下去。
对于手头任务最多的人数只有1人（不妨叫做king）的情况，观察手头任务为mx-1的人数，假设有k人。则其他人数有 n − k − 1 n-k-1 n−k−1人，其余人可以随意排列，即 A n n − k − 1 = n ! ( k + 1 ) ! A_{n}^{n-k-1}=\frac{n!}{(k+1)!} Ann−k−1​=(k+1)!n!​，要使king最后会连续讲两次任务，他只能放在最后，其余k人，随意排列，即 A k k = k ! A_{k}^{k}=k! Akk​=k!。
所以答案为 n ! − A n n − k − 1 ∗ A k k = n ! − n ! k + 1 n!-A_{n}^{n-k-1}*A_{k}^{k}=n!-\frac{n!}{k+1} n!−Ann−k−1​∗Akk​=n!−k+1n!​

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200010;
const int mod  = 998244353;

int n;
int a[maxn];
int p[maxn], inv[maxn];

/*
 * 0 <= a, b < mod
*/
int sub_mod(int a, int b) {
	int res = a - b;
	if (res < 0) res += mod;
	return res;
}

int mul(int a, int b) {
	return 1LL * a * b % mod; 
}

void init() {
	p[0] = 1;
	for (int i = 1; i < maxn; ++i) {
		p[i] = mul(p[i-1], i); 
	}
	
	inv[0]=1;
	inv[1]=1;
	for (int i = 2; i < maxn; ++i) {
	    inv[i] = mul(mod - mod / i, inv[mod%i]);
	}
	
}
int main() {
	int t;
	init();
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; ++i) {
			scanf("%d", &a[i]);
		}
		int mx = a[0];
		for (int i = 1; i < n; ++i) {
			mx = max(mx, a[i]);
		}
		int mxCount = 0;
		for (int i = 0; i < n; ++i) {
			mxCount += (mx == a[i]);
		}
		if (mxCount > 1) {
			printf("%d\n", p[n]);
			continue;
		}
		
		int seCount = 0;
		for (int i = 0; i < n; ++i) {
			seCount += (mx - 1 == a[i]);
		}
		
		int ans = sub_mod(p[n], mul(p[n], inv[seCount+1]));
		printf("%d\n", ans);
	}
	return 0;
} 

这篇关于Jury Meeting(思维/数论)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！