CF1919E

@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();
}