這題是均分紙牌求方案數
我們可以分2種情況討論:
1.當前面部分的平均值>=現在我們要的值
那麼我們可以把所有牌都放到第i個點,現在若有k張牌,則要把k−i∗avek-i*avek−i∗ave張牌放到後面
對答案的貢獻為c(a[i],k−i∗ave)c(a[i],k-i*ave)c(a[i],k−i∗ave),要更新現在的元素值
2.當前面部分平均值<現在我們要的值
那麼我們可以從後面抓i∗ave−ki*ave-ki∗ave−k張牌
由於我們要讓所有部分有aveaveave張牌,所以我們後面需要有ave+i∗ave−kave+i*ave-kave+i∗ave−k張牌,才可以讓抓牌後這部分有aveaveave張牌
所以對答案的貢獻為c((i+1)∗ave−s[i],i∗ave−s[i])c((i+1)*ave-s[i],i*ave-s[i])c((i+1)∗ave−s[i],i∗ave−s[i])
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mo 998244353ll
ll t,n,a[1010],jc[1000010],ijc[1000010],s[1010];
ll qp(ll x,ll y){
ll r=1;
while(y){
if(y&1)r=r*x%mo;
x=x*x%mo;
y>>=1;
}
return r;
}
void get(){
jc[0]=1;
for(ll i=1;i<=1000005;i++)
jc[i]=jc[i-1]*i%mo;
ijc[0]=1;
for(ll i=1;i<=1000005;i++)
ijc[i]=ijc[i-1]*qp(i,mo-2)%mo;
}
ll c(ll x,ll y){
return jc[x]*ijc[x-y]%mo*ijc[y]%mo;
}
int main(){
freopen("gwent.in","r",stdin);
freopen("gwent.out","w",stdout);
scanf("%lld",&t);
get();
while(t--){
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<=n;i++)
s[i]=s[i-1]+a[i];
ll k=s[n]/n,ans=1;
for(ll i=1;i<=n;i++){
ll va=s[i]-k*i;
if(va>=0){
ans=ans*c(a[i],va)%mo;
a[i]-=va;
a[i+1]+=va;
}
else ans=ans*c(-va+k,-va)%mo;
}
printf("%lld\n",ans);
}
}