题解区好像没有和我一样的做法耶……

感觉还是比较简单小清新的……

思路

题目要求最终做完所有操作后，每层楼看到的纸飞机的数量都大于等于 $c$。于是我们可以考虑对于第 $i$ 层楼，他在什么时候恰好达到了 $c$ 个纸飞机。

容易发现，对于 $1$ 到 $n$ 层楼，其恰好达到 $c$ 个纸飞机的时间一定是单调不降的。

证明

证明很显然。

因为如果第 $i$ 层有 $c$ 个纸飞机，那么小于 $i$ 层的楼的纸飞机数量一定大于等于 $c$，所以小于 $i$ 层的楼层一定不会在 $i$ 之后才恰好达到 $c$ 个纸飞机。

设 $d{p}_{i,j,k}$ 为目前考虑到了前 $i$ 层，其中第 $i$ 层的纸飞机数量恰好等于 $c$ 的时间点为 $j$。对于 $j$ 之后的时间和 $i$ 之后的层数，我们暂时不予考虑。其中，$j$ 之前的时间中，有 $k$ 个位置我们给他空出来了，留着以后填（延迟），这 $k$ 个位置的填的数一定是大于 $i$ 的。满足以上条件的方案数废话。

考虑 $d{p}_{i,j,k}$，我们枚举 $i-1$ 恰好 $c$ 个纸飞机的时间 $p$。则 $[p+1,j]$ 一段时间中填的数，一定是大于 $i-1$ 的（因为 $i-1$ 已经达到 $c$ 了，根据题意，不能再填了）。

我们要求小于等于 $j$ 的时间中，有恰好 $c$ 个大于等于 $i$ 的飞机，而 $[p+1,j]$ 又全是大于等于 $i$ 的，则 $[1,p]$ 中一定恰有 $c-j+p$ 个。

另外，这 $c$ 个中，我们还要挑出 $k$ 个给后面留着。

于是有：
$$d{p}_{i,j,k}=d{p}_{i-1,p,c-j+p}\times \left(\genfrac{}{}{0ex}{}{c}{k}\right)$$

其中 $c-j+p$ 一定比 $c$ 小，所以 DP 的第三维 $k$ 我们枚举到 $c$ 即可。

先贴一下暴力方便理解

#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];
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 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=0;i<=c;i++) dp[c][i]=C(c,i);
		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
				for(int k=0;k<=c;k++)
					for(int p=j;p>=1;p--)
					{
						if(c-j+p<0) break;
						dpp[j][k]=(dpp[j][k]+dp[p][c-j+p]*1ll*C(c,k)%mod)%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;
		}
		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;
}

非常优雅的转移！一看就非常有前途！我们注意到 DP 的状态数只有 $n\times m\times c$ 个，是符合要求的，瓶颈在于转移时枚举 $p$。

可以先不要看下面自己想一下如何优化（如果理解了就不是很难）。

注意到随着 $p$ 的减小，$c-j+p$ 一定是依次递减。也就是说，如果我们这一次用 $d{p}_{i-1,p,kk}$ 转移，下一次就一定用 $d{p}_{i-1,p-1,kk-1}$。前缀和一下即可。

代码

答案即为 $d{p}_{n,m,0}$（$n$ 达到 $c$ 的时间一定是在 $m$，这个易证）。

时间复杂度 $O(nmc)$，可过。

容易滚动数组。

#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];//s为前缀和数组 
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 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=0;i<=c;i++) dp[c][i]=C(c,i);
		for(int j=1;j<=m;j++)
			for(int k=0;k<=c;k++) 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++)
				for(int k=0;k<=c;k++)
					dpp[j][k]=s[j][c]*1ll*C(c,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++) 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;
}

代码是不是还挺煎蛋（？

书接下文

可以挑战一下本题的加强版。