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;
} 
上一篇:背包问题之多重背包


下一篇:P4180 [BJWC2010]严格次小生成树