直接写出来最基础的转移方程，发现假如去掉单调递增的限制就是裸的斜率优化。
所以离散化一下，在线段树上维护凸包就可以解决单调增的限制。
当然cdq分治也可以。
考虑逐位确定，那么现在的问题是已经知道了前面的字母集合，求出剩余部分的方案数。
假如已经知道了每种字母还有多少个，那么只要枚举k!种置换就可以算出方案。
对于每种字母剩余若干个的方案数，可以通过记忆化搜索预处理出来。
考虑给字母数量sort一下，这样状态数就合法了。
另外一种好的做法是直接在记忆化搜索中按位确定，对于相对相同的集合记为同一种状态，用hash存。
考虑枚举字典序相邻的两个集合的第一个不相同的位，那么这两个集合在这一位上只能差1，并且后面的方案是确定的。
那么只要枚举这一位上填哪个数就可以确定第m位填谁，而这样的方案数之和前面有关。
发现这个式子如果枚举位置和数的差，那么需要求的就是一列组合数的和。
直接算就完了。
原文：https://www.cnblogs.com/hzoi-cbx/p/12363912.html