@Explodingkonjac 学长讲的做法，题解区有一篇讲这个的，但是感觉细节真的好多……
我们先尝试构造出来一个合法序列。怎么构造呢？先枚举 \(\sum a_i=s\)，然后先将序列 \(a\) 设为 \(\max(p_n,0)\) 个 \(1\) 后面接 \(\max(p_n,0)-s\) 个 \(-1\)，也就是先到最大值再到最终值。
然后考虑往这个数列中插入若干 \(\{-1,1\}\) 这个序列。画到一个折线图上，发现这就相当于增加一块凹陷。不难发现，对于一个有解的 \(s\)，这样一定能构造出解。
设新前缀和序列为 \(p'\) 同时，在一个 \(p_i'=k\) 的位置后面插入一个 \(\{-1,1\}\) 能使 \(k,k-1\) 在 \(p'\) 的出现次数增加 \(1\)。于是在构造的同时就可以计数了！
具体地，从大往小考虑 \(x\) 的出现次数。设 \(x\) 在 \(p\) 中出现 \(a_x\) 次，\(p'\) 中 \(b_x\) 次，则要通过插入 \(\{-1,1\}\) 的操作将 \(b_X\) 加到 \(a\)。反过来，一共要将 \(a_x\) 个 \(x\) 分到 \(b_x\) 个集合中，插板法，贡献为 \(\binom{a-1}{b-1}\)。然后 \(b_{x-1}\) 会加上 \(a_x-b_x\)，继续往下推即可。
细节包括但不限于：
-
\(p'\) 要考虑一开始的 \(0\) 否则一开始下降的情况统计不到。
-
\(a_x=0\) 的情况要注意一下。
-
等等。
code：
点击查看代码
int n,m,fac[N],ifac[N],c[N],b[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
il int binom(int x,int y){
if(x<0||y<0||x<y)return 0;
return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
il int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return ret;
}
void Yorushika(){
scanf("%d",&n);
int mx=0;
rep(i,0,n+n)c[i]=0;
c[n]=1;
rep(i,1,n){
int x;scanf("%d",&x);
c[x+n]++,mx=max(mx,x+n);
}
fac[0]=1;
rep(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
drep(i,n-1,0)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
int ans=0;
rep(j,0,n+n){
if(!c[j])continue;
int x=n,res=1;
rep(i,0,n+n)b[i]=0;
b[n]=1;
rep(i,1,mx-n)b[++x]++;
rep(i,1,max(mx,n)-j)b[--x]++;
bool fl=1;
if(!fl)continue;
drep(i,n+n,0){
if(!c[i]){if(b[i]){res=0;break;}continue;}
res=1ll*res*binom(c[i]-1,b[i]-1)%mod;
if(i)b[i-1]+=c[i]-b[i];
}
ans=Mod(ans,res);
}
printf("%d\n",ans);
}
signed main(){
int t=1;
scanf("%d",&t);
while(t--)
Yorushika();
}