A K-ary heap of size n is an array [a0,a1,…,an1], and for each pair of indices i and j which satisfy 0≤i≤n10 leq i leq n - 10≤i≤n1, Ki+1≤j≤min{Ki+K,n1}K cdot i + 1 leq j leq min lbrace K cdot i + K, n - 1 rbraceKi+1≤j≤min{Ki+K,n1}, aja_jaj is strictly greater than aia_iai. Considering all possible K-ary heaps of size n which are also permutations obtained from 1 to n, let us write down these heaps in lexicographical order, and then label them starting from 1. For example, when n = 3, K = 2, there are two possible heaps [1, 2, 3] and [1, 3, 2], which are labeled 1 and 2 respectively. Given a K-ary heap of size n which is also a permutation obtained from 1 to n, we want you to find the label of this heap after doing the aforementioned process. As the answer can be very large, we request you to report the label modulo .
A K-ary heap of size n is an array [a0,a1,…,an−1][a_0, a_1, ldots, a_{n - 1}][a0,a1,…,an−1], and for each pair of indices i and j which satisfy 0≤i≤n−10 leq i leq n - 10≤i≤n−1, K⋅i+1≤j≤min{K⋅i+K,n−1}K cdot i + 1 leq j leq min lbrace K cdot i + K, n - 1 rbraceK⋅i+1≤j≤min{K⋅i+K,n−1}, aja_jaj is strictly greater than aia_iai. Considering all possible K-ary heaps of size n which are also permutations obtained from 1 to n, let us write down these heaps in lexicographical order, and then label them starting from 1. For example, when n = 3, K = 2, there are two possible heaps [1, 2, 3] and [1, 3, 2], which are labeled 1 and 2 respectively. Given a K-ary heap of size n which is also a permutation obtained from 1 to n, we want you to find the label of this heap after doing the aforementioned process. As the answer can be very large, we request you to report the label modulo (109+7)(10^{9} + 7)(109+7).
标签： HBC52021HistoryK-ary Heap题解
