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

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

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

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

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

• 插到末尾
• 插到比他小的前
• 插到和它相等的数，然后后面退了一位后刚好满足

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

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

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

考虑这一次插还是不插。

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

如果当前插的话，那就转移至 × ( k + 1 ) → f ( i + 1 , j , k ) \times (k+1)\to f(i+1,j,k) × ( k + 1 ) → 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]);