CF1569C Jury Meeting

原题传送门

题目大意:$n$个人召开会议,第$i$个成员有$a_i$项提议。先决定他们的顺序。然后按照顺序发言，如果当前人有提议，提出。否则，跳过。按顺序重复这个过程，第$n$个人完成后再回到第$1$个人。如果没有人连续提出提议，则这个顺序是好的.求所有好的顺序的数量。答案模 998244353。

思路：分三种情况讨论。我们计最大值为$mx$，个数为$tot$，次大值为$mx'$，个数为$cnt$

第一种情况：$mx-mx'>1$时，不管怎么排列，最终$mx$都会剩余至少两次，就会连续提议，不符合条件，结果为$0$

第二种情况：$tot>1$时，不管如何排列都是符合条件的，结果为$n！$

第三种情况：$mx=mx'+1$并且$tot=1$时，对于这种情况来说，我们发现，只要在$mx$后面有一个$mx'$时，就是符合条件的序列。那我们只需要考虑$mx$和$mx'$的次序，显然我们发现对于这$cnt+1$个数，只有$mx$这个数排在最后这种情况不符合，那么符合条件的概率期望为$\frac{cnt}{cnt+1}$,那么对这$n$个数的全排列来说，符合条件的排列为:$n!\frac{cnt}{cnt+1}$

PS:习惯预处理阶乘，然后直接除以$cnt+1$就会出错，因为预处理的阶乘是模$mod$意义下的，这就导致直接除出问题了，所以除以$cnt+1$要转变为乘以模$mod$意义下的逆元

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=998244353;
typedef long long ll;
ll t,n,a[N],fac[N];
ll power(ll a,ll b){
    ll res=1;
    for(;b;b>>=1){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        ll maxn=0;
        fac[0]=1;
        for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            maxn=max(maxn,a[i]);
        }
        ll cnt=0,tot=0;
        for(int i=1;i<=n;i++){
            if(a[i]==maxn) tot++;
            if(a[i]==maxn-1) cnt++;
        }
        if(tot>1)  cout<<fac[n]<<endl;
        else if(tot==1&&cnt!=0) cout<<fac[n]*cnt%mod*power(cnt+1,mod-2)%mod<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}