题目
题意:给定
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;
}