CF1569C Jury Meeting

原题传送门

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

思路：分三种情况讨论。我们计最大值为$mx$，个数为$tot$，次大值为$m{x}^{\prime }$，个数为$cnt$

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

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

第三种情况：$mx=m{x}^{\prime }+1$并且$tot=1$时，对于这种情况来说，我们发现，只要在$mx$后面有一个$m{x}^{\prime }$时，就是符合条件的序列。那我们只需要考虑$mx$和$m{x}^{\prime }$的次序，显然我们发现对于这$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;
}