CodeForces 1569C Jury Meeting

题目链接：CodeForces 1569C Jury Meeting

题目大意：
有\(n\)个人开会，每个人都有一些要说的任务，将这些人按一定顺序排列，使他们按顺序每人说一个自己的任务，如果一轮结束还有人有任务没说，则继续下一轮，说完所有任务的人直接跳过。
如果一个人连续说了两个任务，则这种排列不可行，求可行的排列数量。

题解：
很显然，会有一个人连续说两个任务说明在某一轮中他是最后一个发言的并且除他之外的其他人都已经说完了所有任务，因此在下一轮中他成为了第一个发言的人。
因此我们可以从所有人的任务数中的最大值的角度考虑这个问题。

1. 如果最大值的数量不唯一，则这些任务数量最大的人一定是在同一轮说完所有任务的，不会出现不可行的情况，则所有人可以任意排列组合，答案为\(n!\)；
2. 如果最大值的数量唯一，且最大值与第二大值的差大于\(1\)，则无论如何排列，都会出现任务最多的人单独至少两轮，所以答案为\(0\)；
3. 如果最大值的数量唯一，且最大值与第二大值的差为\(1\)，则按如下方法考虑：
   直接求可行的排列较为复杂，可以通过间接的方法来求，求出全排列减去不可行的排列数量即为所求。
   设第二大值的人数为\(m\)，如果出现任务最多的人连续讲两次的情况，说明他排在所有任务数第二多的人后面，则这样的排列有\(m!\)种，
   将剩下的人按照插空法（不知道叫什么方法，反正我喜欢这么叫(●‘?‘●)）排列进去，可知排列数为\(\frac{n!}{(m+1)!}\)，
   所以不可行的排列数量为\(m! \times \frac{n!}{(m+1)!} = \frac{n!}{m+1}\)，
   因此可行的排列数量为\(n! - \frac{n!}{m+1} = \frac{m}{m+1} \times n!\)。

阶乘可以通过预处理得到，由于要取模，所以计算\(\frac{1}{m+1}\)时需要求逆元，可以用费马小定理和快速幂求得。

#include <iostream>
#include <map>
using namespace std;
#define LL long long
const LL mod = 998244353;
 
LL fac[200010];
int t, n;
 
void init() {
    fac[0] = 1ll;
    for (int i = 1; i <= 200000; ++i) {
        fac[i] = (LL)i * fac[i - 1] % mod;
    }
}
 
LL qpow(LL x, LL k) {
    LL res = 1ll;
    while (k) {
        if (k & 1ll) res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return res;
}
 
int main() {
    init();
    scanf("%d", &t);
    while (t--) {
        map <int, int> mat;
        scanf("%d", &n);
        for (int i = 1, x; i <= n; ++i) {
            scanf("%d", &x);
            mat[x]++;
        }
        if (mat.rbegin()->second > 1) {
            cout << fac[n] << endl;
        } else if (mat.rbegin()->first - (++mat.rbegin())->first > 1) {
            cout << 0 << endl;
        } else {
            LL inv = qpow((++mat.rbegin())->second + 1ll, mod - 2ll);
            LL ans = (inv * (++mat.rbegin())->second % mod * fac[n]) % mod;
            cout << ans << endl;
        }
    }
    return 0;
}

CodeForces 1569C Jury Meeting

原文：https://www.cnblogs.com/IzumiSagiri/p/15249580.html