CF2182D Christmas Tree Decoration

思路

手玩样例后发现这个拿装饰品的机制和班上轮换做清洁有点像啊。
不难发现在合法情况下，最少的拿取次数最多比最多的拿取次数少 $1$ 次。
那我们先判断是否合法，方法如下：

找到对应装饰品最多的一个人，设他的对应盒子中有 $mx$ 个装饰品。
将其他人的对应装饰品补足至 $mx-1$，不够的部分从 $p_0$ 中减掉。若在某一步 $p_0$ 不够了，则方案数为 $0$。

然后此时一定存在合法情况，我们考虑如何计算合法排列数。
首先这个排列中每个人的挂装饰品次数应当形如 $mx,\cdots,mx,mx-1,\cdots,mx-1$。
先扫描一遍整个数组，找到 $mx$ 有多少个，设它有 $a$ 个，则 $mx-1$ 有 $n-a$ 个。
此时分类讨论：

若 $p_0\le n-a$，则 $p_0$ 无法将所有 $mx-1$ 补到 $mx$，那么在补足后将会有 $a+p_0$ 个 $mx$，$n-a-p_0$ 个 $mx-1$，则答案为 $C_{n-a}^{p_0}\cdot A_{a+p_0}^{a+p_0}\cdot A_{n-a-p_0}^{n-a-p_0}$。
若 $p_0>n-a$，则 $p_0$ 可以将所有值都补至 $mx+\lfloor\frac{p_0-(n-a)}{n}\rfloor$，再将剩下的值给最前面的一部分即可，不会限制排列，所有情况均合法，答案为 $A_n^n$。

这里面求组合数时因为要取模，还要用到逆元，就不多赘述了，不熟悉逆元的同学可以去看看这个。

代码

#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
		inline void read(T &x,Args&...args){
		read(x);
		read(args...);
	}
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=55,mod=998244353;  
int n,T,p[N];
int calc(int n,int x){
	n%=mod;
	if(x==0)return 1;
	if(x==1)return n;
	int hf=x/2,el=x%2;
	int hfv=calc(n,hf);
	int elv=calc(n,el);
	return hfv*hfv%mod*elv%mod;
}
int A(int m,int n){
	int ans=1;
	rep(i,n-m+1,n){
		ans*=i;
		ans%=mod;
	}
	return ans;
}
int C(int m,int n){
	int ans=A(m,n);
	rep(i,1,m){
		int inv=calc(i,mod-2);
		ans*=inv;
		ans%=mod;
	}
	return ans;
}
signed main(){
	read(T);
	while(T--){
		read(n);
		rep(i,0,n)read(p[i]);
		int mx=0;
		rep(i,1,n){
			mx=max(mx,p[i]);
		}
		int a=0,ans=1;
		rep(i,1,n){
			if(p[i]<mx-1){
				p[0]-=(mx-1-p[i]);
				p[i]=mx-1;
				if(p[0]<0)ans=0;
			}
			if(p[i]==mx){
				a++;
			}
		}
		int m=p[0];
		if(m<=n-a){
			ans*=C(m,n-a)*A(a+m,a+m)%mod*A(n-a-m,n-a-m)%mod;
		}
		else{
			ans*=A(n,n);
		}
		print(ans);puts("");
	}
}