To solve Div1 C, Div2 E

Let's calculate two functions:

dp[i] — How many [i] permutations exists, where last element is i and will return correct maximal value.

dpsum[i] — How many [i] permutations exists, where element i is in one of the last k positions and algorithm returns correct maximal value.

Then we can calculate these functions in linear time:

To calculate dp[i] we simply append i to the end of all the [i-1] permutations, where i - 1 is located in one of the last k positions and algorithm will return correct maximum value.

dp[i] = dpsum[i - 1]

To calculate dpsum[i] we must remove all permutations, where maximum value will be located outside the last k elements of permutation from dpsum[i - 1]. Then append new element to the end of permutation, it must be less than previous maximum value. So multiplying by (i - 1) we add this new element and increase all larger, equal permutation element values by one, so we get [i] permutations, where i is located in range [i - k + 1, i - 1]. Lastly, we must append all permutations which have maximal value i in the last position of [i] permutation, we calculated it in dp[i].

Then we can calculate the number of all good permutations, where correct maximum value is returned by algorithm.

Lets fix position i, where maximum value n will be located. Then first i element prefix of permutation must return correct maximal value and maximal element is in the last position of permutation formed by prefix, so we use dp[i]. We choose order of last n - i elements in (n - i)! ways. Suffix of last (n - i) elements forms a permutation.

Then we must merge these two permutations together by merging all elements except maximal n together. This can be done in ways.

Then the number of bad permutation is count of all [n] permutations minus good permutation count;

answer = n! - good_perm_cnt