请先读一下这篇文章。

书接上文，我们只需要稍微动下小手术即可。

我们考虑对于 $d{p}_{i,j,k}$，依旧枚举 $p$（定义与上文一致），我们要求小于等于 $j$ 的时间中，有恰好 $c$ 个大于等于 $i$ 的飞机，而 $[p+1,j]$ 又全是大于等于 $i$ 的，且 $[1,j]$ 中有一些已经确定的位置大于等于 $i$，我们记这个值为 $q$（可以容易前缀和预处理），则 $[1,p]$ 中一定恰有 $c-q-j+p+pp$ 个，其中 $pp$ 为 $[1,p]$ 中大于等于 $i$ 的数量。

在 $p$ 的变化过程中，$pp$ 也在变化，所以我们需要对前缀和做下小手术。

如果我们这一次用 $d{p}_{i-1,p,kk}$ 转移：

• 若 $a_p\ge i$，下一次就一定用 $d{p}_{i-1,p-1,kk}$。
• 否则下一次一定用 $d{p}_{i-1,p-1,kk-1}$。

另外，在 $d{p}_{i,j,k}$ 中，如果 $j$ 时刻后面有第 $i$ 层发出的飞机（可以预处理），根据题意，需要将这个状态特判为 $0$。

依旧优雅~

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,c,m,a[10005];
int dp[10005][105],dpp[10005][105],s[10005][105];
int ksm(int x,int y)
{
	if(y==1) return x;
	if(!y) return 1;
	int mid=ksm(x,y>>1);
	if(y&1) return mid*1ll*mid%mod*x%mod;
	return mid*1ll*mid%mod;
}
int jie[10005],njie[10005];
int C(int x,int y)
{
	if(x<y) return 0;
	return jie[x]*1ll*njie[y]%mod*njie[x-y]%mod;
}
int q[10005][105],h[10005][105];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	jie[0]=1,njie[0]=1;
	for(int i=1;i<=10000;i++) jie[i]=jie[i-1]*1ll*i%mod,njie[i]=ksm(jie[i],mod-2);
	cin>>t;
	while(t--)
	{
		cin>>n>>c>>m;
		for(int i=1;i<=m;i++) cin>>a[i];
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
				if(j<=a[i]) q[i][j]=(q[i-1][j]+1)%mod;
				else q[i][j]=q[i-1][j];
		}
		for(int i=1;i<=n;i++) h[m+1][i]=0;
		for(int i=m;i>=1;i--)
		{
			for(int j=1;j<=n;j++)
				if(j==a[i]) h[i][j]=(h[i+1][j]+1)%mod;
				else h[i][j]=h[i+1][j];
		}
		for(int i=0;i<=c-q[c][1];i++) 
		{
			if(h[c+1][1]) continue ;
			dp[c][i]=C(c-q[c][1],i);
		}
		for(int j=1;j<=m;j++)
			for(int k=0;k<=c;k++) 
				if(a[j]) s[j][k]=(dp[j][k]+s[j-1][k])%mod;
				else s[j][k]=(dp[j][k]+s[j-1][k-1])%mod;
		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(h[j+1][i]) continue ;
				for(int k=0;k<=c-q[j][i];k++)
				{
					if(c-(j-j)-q[j][i]>=0)
					dpp[j][k]=s[j][c-(j-j)-q[j][i]]*1ll*C(c-q[j][i],k)%mod;
				} 
			}
			for(int j=1;j<=m;j++)
				for(int k=0;k<=c;k++) dp[j][k]=dpp[j][k],dpp[j][k]=0;
			for(int j=1;j<=m;j++)
				for(int k=0;k<=c;k++) 
					if(a[j]) s[j][k]=(dp[j][k]+s[j-1][k])%mod;
					else s[j][k]=(dp[j][k]+s[j-1][k-1])%mod;
		}
		cout<<dp[m][0]<<"\n";
		for(int j=1;j<=m;j++)
			for(int k=0;k<=c;k++) dp[j][k]=0;
	}
	return 0;
}

::::