C. Jury Meeting

C. Jury Meeting(组合数）

题目入口

思路
我们发现，每一次先消去的是最小的人，观察最后留下的两个不同的数，一定是最大的和次大的，并且我们发现，若最大的数个数多于两个，最后一定是在那几个数中循环，此时答案无关排列位置，就是n!，而当最大的数只有一个，以4 3 3 为例，只有当3 3 4时不合法，其余都合法，即最大数在所有次大数后面时不合法，答案用所有排列数减去不合法数即可
(刚开始怕爆long long，用来qmul，结果反而tle了第8个点)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
const int N=2e5+10,mod=998244353;
int fac[N];
int a[N];
unordered_map<int,int> mp;
int qmul(int a,int n)
{int res=0;while(n){if(n&1) res=(res+a)%mod;a=2*a%mod;n>>=1;}return res;
}
int qpow(int a,int n)
{int res=1;while(n){if(n&1) res=res*a%mod;a=a*a%mod;n>>=1;}return res;
}
void init()
{fac[0]=1;for(int i=1;i<=N-5;i++)fac[i]=fac[i-1]*i%mod;
}
int C(int a,int b)
{int res=1;for(int i=1,j=a;i<=b;i++,j--){res*=j;res%=mod;res*=qpow(i,mod-2);res%=mod;}return res;
}
int A(int a,int b)
{return C(a,b)*fac[b]%mod;
}
signed main()
{init();cin>>t;while(t--){mp.clear();int n;cin>>n;int maxx=-1;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;if(maxx<a[i]) maxx=a[i];}int max2=-1;for(int i=1;i<=n;i++)if(max2<a[i]&&a[i]!=maxx) max2=a[i];//cout<<"maxx="<<maxx<<"max2="<<max2<<endl;//cout<<"mp[maxx]="<<mp[maxx]<<"mp[max2]="<<mp[max2]<<endl;if(mp[maxx]>=2) cout<<fac[n]<<endl;else if(maxx>max2+1) cout<<"0"<<endl;else{int num=mp[max2];int res=(A(n,n)+mod-A(n,n)%mod*qpow(num+1,mod-2)%mod)%mod;cout<<res<<endl;}//cout<<"A(6,6)"<<A(6,6)<<endl;}return 0;
}