- [A. Bermutation]
- [B. Grid]
- [C. Heap]
- [D. Lines]
- [E. Yet Another Problem About Permutations]
- [F. Strange Sequence]
- [G. Shortest Accepted Word]
- [H. Work]
题意：考虑一个长度为$n$的$d$叉堆$a_1,a_2,\dots,a_n$。对于$1 \le i \le n, 1 \le j \le n$并且$(i-1) \cdot d + 2 \le j \le i \cdot d + 1$都有$a_j > a_i$。
现在给出一个长度为$n$的排列，满足$d$叉堆的性质。求出有多少字典序不大于它的，也满足$d$叉堆性质的排列，对$10^9+7$取模。
题解：首先建出这棵$d$叉树来，对于每个点$i$，预处理出$size(i)$表示这棵子树的大小，$dp(i)$表示用$1$到$size(i)$填这棵子树的方案数。与处理点组合数，这个可以很方便的计算出来。
接下来考虑计算有多少排列字典序大于给出的排列（不直接计数是因为复杂度会多个$n$）。从小到大枚举每个前缀，然后计算这个前缀固定的情况下，满足$d$叉堆性质的排列个数。
固定前缀$i$之后，我们可以知道一些节点$x$的第$y$个子树还没有填满，可以得到限制条件：节点$x$的第$y$个子树里的每个数都要大于$a_x$。除此之外，点$i$所在的子树里每个数都要大于$a_i$。
然后问题等价于：有若干个不相同的数$a_1,a_2,\dots,a_n$，你需要分成$m$组，第$i$组大小为$s_i$，并且每个数都要大于$a_i$，求方案数。这个是一个经典问题，按照$a_i$从大到小依次分配即可，就是一些组合数运算一下。
算出上述问题的解之后，每个子树还需要内部分配这些数，就是我们刚才预处理出来的$dp(\cdot)$。
复杂度$O(n^2)$。