插入数计数类 / 转为换行类dp：AT_agc024_e

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135078944

https://www.luogu.com.cn/problem/AT_agc024_e

首先题目可以转化成每次插入一个数，满足字典序递增。

如果只考虑暴力dfs，先别上dp，想想怎么合法和不算重。

合法，也就是插入数有3种情况

• 插到末尾

• 插到比他小的前

• 插到和它相等的数，然后后面退了一位后刚好满足

前2种是好做的，但如果要处理第3种，我们要维护一堆奇奇怪怪的东西。但我们还要考虑不算重！插在第3中的任意位置都会算重，所以其实可以全部规约到第2种。

因此我们钦定只能插入至连续段的末尾。

现在变成了经典的插入数问题，显然从小到大插到 $j$ ，有 $k+1$ 个合法位置。然后到这里还要来个插了 $i$ 次。

考虑这一次插还是不插。

不插，就转移到 $k-1$ 。如果 $k$ 已经是0了，那就要枚举下一个数了，转移到 $f(i,j+1,i)$ （因为接下来所有位置都可以插）

如果当前插的话，那就转移至 $\times (k+1)\to f(i+1,j,k)$ ，之所以要乘这个系数，是考虑到插入的数之间是有顺序的。

n=read(); k=read(); mo=read(); 
dp[0][1][0]=1; 
for(i=0; i<=n; ++i)
	for(j=1; j<=k; ++j) 
		for(t=n; t>=0; --t) {
			if(t) Add(dp[i][j][t-1], dp[i][j][t]); 
			else Add(dp[i][j+1][i], dp[i][j][t]); 
			Add(dp[i+1][j][t], dp[i][j][t]*(t+1)); 
		}
printf("%lld", dp[n][k][0]);