C. Maximum Element

一天，Petya 在解决一个非常有趣的问题。尽管他使用了许多优化技巧，他的程序仍然获得了超时（Time limit exceeded）的 verdict。Petya 对他的程序进行了彻底分析，发现他用于在包含 #cf_span[n] 个正整数的数组中寻找最大值的函数太慢了。绝望之下，Petya 决定使用一个出人意料的优化，引入参数 #cf_span[k]，于是他的函数现在包含以下代码： 该函数迭代检查数组元素，记录中间最大值，如果在连续 #cf_span[k] 次迭代后该最大值仍未改变，则将其作为答案返回。 现在 Petya 想要知道他函数的错误率。他请你找出从 #cf_span[1] 到 #cf_span[n] 的所有排列中，使得该函数返回值不等于 #cf_span[n] 的排列数量。由于这个数可能非常大，请输出答案对 #cf_span[109 + 7] 取模的结果。 输入仅一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 106]），用空格分隔，分别表示排列的长度和参数 #cf_span[k]。 请输出该问题的答案，对 #cf_span[109 + 7] 取模。 第二个样例中的排列： #cf_span[[4, 1, 2, 3, 5]], #cf_span[[4, 1, 3, 2, 5]], #cf_span[[4, 2, 1, 3, 5]], #cf_span[[4, 2, 3, 1, 5]], #cf_span[[4, 3, 1, 2, 5]], #cf_span[[4, 3, 2, 1, 5]]. ## Input 输入仅一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 106]），用空格分隔，分别表示排列的长度和参数 #cf_span[k]。 ## Output 请输出该问题的答案，对 #cf_span[109 + 7] 取模。 [samples] ## Note 第二个样例中的排列：#cf_span[[4, 1, 2, 3, 5]], #cf_span[[4, 1, 3, 2, 5]], #cf_span[[4, 2, 1, 3, 5]], #cf_span[[4, 2, 3, 1, 5]], #cf_span[[4, 3, 1, 2, 5]], #cf_span[[4, 3, 2, 1, 5]].

Let $ n $ and $ k $ be given integers with $ 1 \leq n, k \leq 10^6 $. Let $ \pi $ be a permutation of $ \{1, 2, \dots, n\} $. Define the function $ f(\pi, k) $ as follows: - Initialize $ m = 0 $. - For $ i = 1 $ to $ n $: - If $ \pi_i > m $, set $ m = \pi_i $. - If $ i \geq k $ and $ m $ has not changed in the last $ k $ iterations (i.e., $ \pi_{i-j} \leq m $ for all $ j = 1, 2, \dots, k $), then return $ m $. The function terminates early if, after $ k $ consecutive elements that do not update the current maximum, it returns the current maximum. We are to compute the number of permutations $ \pi $ of $ \{1, 2, \dots, n\} $ such that $ f(\pi, k) \ne n $, modulo $ 10^9 + 7 $. --- ### Formal Problem Statement: Let $ S = \{1, 2, \dots, n\} $. Let $ \mathcal{P}_n $ be the set of all permutations of $ S $. Define the **early termination condition**: For a permutation $ \pi = (\pi_1, \pi_2, \dots, \pi_n) $, let $ m_i = \max\{\pi_1, \dots, \pi_i\} $. The function terminates at the smallest index $ i \geq k $ such that: $$ m_i = m_{i-1} = \dots = m_{i-k+1} $$ (i.e., the maximum has not increased in the last $ k $ steps), and returns $ m_i $. We say the function **fails** on $ \pi $ if the returned value is **not** $ n $. We are to compute: $$ \left| \left\{ \pi \in \mathcal{P}_n \mid f(\pi, k) \ne n \right\} \right| \mod (10^9 + 7) $$ --- ### Key Observations: - The function returns $ n $ **if and only if** the maximum element $ n $ appears **before** any sequence of $ k $ consecutive elements that do not update the maximum. - Equivalently, the function **fails** if $ n $ appears **after** a block of $ k $ consecutive elements, all less than the current maximum **at the time**, and that current maximum is **less than $ n $**. - Therefore, the function fails **iff** the maximum value $ n $ appears **at position $ i > k $**, and **in the $ k $ positions immediately preceding $ i $**, none of the elements is $ n $, and **the maximum among the first $ i-1 $ elements is unchanged for $ k $ steps**. But note: if $ n $ appears at position $ i $, then **before** position $ i $, the running maximum is some $ m < n $. The function will return $ m $ **if** at some point $ j \geq k $, the last $ k $ elements (from $ j-k+1 $ to $ j $) are all $ \leq m $, and $ m $ is not updated again until after $ j $. So, the function returns a value $ < n $ **iff** the element $ n $ appears **after** the first occurrence of a run of $ k $ consecutive elements that do not increase the current maximum. Thus, the function **fails** if and only if **the maximum element $ n $ is not among the first $ k $ elements**, and **in the prefix before $ n $, there is a run of $ k $ consecutive elements that do not update the running maximum**. But note: if $ n $ is at position $ i > k $, then the prefix $ \pi_1, \dots, \pi_{i-1} $ consists of $ i-1 $ elements all less than $ n $. Let $ M = \max\{\pi_1, \dots, \pi_{i-1}\} $. Then, if at some point $ j \in [k, i-1] $, we have that the last $ k $ elements up to $ j $ are all $ \leq M $, and $ M $ was set at position $ j - k + 1 $ or earlier, then the function will terminate at $ j $ and return $ M < n $, **before** seeing $ n $. So, the function fails **iff** $ n $ appears **after position $ k $**, and **in the prefix before $ n $, there exists a position $ j \in [k, i-1] $** such that the maximum in $ \pi_1, \dots, \pi_j $ is equal to the maximum in $ \pi_{j-k+1}, \dots, \pi_j $, i.e., the maximum has not increased in the last $ k $ steps. This is equivalent to: **the first $ k $ elements do not contain $ n $, and the maximum among the first $ i-1 $ elements (i.e., before $ n $) is set at or before position $ i-k $**. In other words: Let $ p $ be the position of $ n $ in the permutation. Then the function returns $ < n $ **iff** $ p > k $, and the maximum of the first $ p-1 $ elements appears at or before position $ p - k $. That is, the maximum among $ \pi_1, \dots, \pi_{p-1} $ is among $ \pi_1, \dots, \pi_{p-k} $. Let $ M_{p-1} = \max\{\pi_1, \dots, \pi_{p-1}\} $. Then $ M_{p-1} $ must occur at some index $ \leq p - k $. So, for a fixed position $ p $ of $ n $, with $ p > k $, the number of permutations where $ n $ is at position $ p $, and the maximum of the first $ p-1 $ elements occurs in the first $ p - k $ positions, is: - Choose $ p-1 $ elements from $ \{1, \dots, n-1\} $ to precede $ n $: $ \binom{n-1}{p-1} $ ways. - Among these $ p-1 $ elements, the maximum must be among the first $ p - k $ elements. - The number of ways to arrange these $ p-1 $ elements such that the maximum of them is in the first $ p - k $ positions: Let $ M' = \max\{\text{first } p-1 \text{ elements}\} $. We require $ M' $ to be in position $ \leq p - k $. The maximum element among the $ p-1 $ elements can be placed in any of the first $ p - k $ positions. The remaining $ p-2 $ elements can be arranged arbitrarily in the other $ p-1 $ positions. Actually, the probability that the maximum of $ p-1 $ distinct elements appears in the first $ p - k $ positions is $ \frac{p - k}{p - 1} $, since all positions are symmetric. So, for fixed $ p $, number of such permutations is: $$ \binom{n-1}{p-1} \cdot (p-1)! \cdot \frac{p - k}{p - 1} = \binom{n-1}{p-1} \cdot (p-2)! \cdot (p - k) $$ Wait — better: Total number of ways to arrange the first $ p-1 $ elements: $ (p-1)! $ Number of those where the maximum of the first $ p-1 $ elements is among the first $ p - k $ positions: There are $ p - k $ positions where the global max of the $ p-1 $ elements can be placed (must be one of them), and the rest $ p-2 $ elements can be arranged arbitrarily: So: $ (p - k) \cdot (p - 2)! $ Thus, for fixed $ p \in \{k+1, k+2, \dots, n\} $, the number of permutations where $ n $ is at position $ p $ and the function fails is: $$ (p - k) \cdot (p - 2)! \cdot (n - p)! $$ Why? Because after placing $ n $ at position $ p $, and arranging the first $ p-1 $ elements with the max in the first $ p-k $ positions (in $ (p - k) \cdot (p - 2)! $ ways), the remaining $ n - p $ elements after $ n $ can be arranged arbitrarily in $ (n - p)! $ ways. But wait — the elements after $ n $ don't matter, because the function already terminated before reaching them. So, the total number of failing permutations is: $$ \sum_{p = k+1}^{n} (p - k) \cdot (p - 2)! \cdot (n - p)! $$ But note: this counts only permutations where $ n $ is at position $ p > k $, and the maximum of the prefix before $ n $ is among the first $ p - k $ elements. This is exactly the condition for early termination before seeing $ n $. So, the answer is: $$ \boxed{ \sum_{p = k+1}^{n} (p - k) \cdot (p - 2)! \cdot (n - p)! } \mod (10^9 + 7) $$ We can reindex: let $ i = p - k $, then $ p = i + k $, and $ i $ runs from $ 1 $ to $ n - k $: $$ \sum_{i=1}^{n-k} i \cdot (i + k - 2)! \cdot (n - k - i)! $$ But perhaps better to leave as is. Note: When $ k \geq n $, then $ p > k $ is impossible (since $ p \leq n $), so the sum is empty → answer = 0. Indeed, if $ k \geq n $, then the function will not terminate early (since it needs $ k $ consecutive non-updates, but the array is only length $ n \leq k $, so it will scan all elements and return $ n $). So answer = 0. Also, if $ k = 1 $, then after every step, if no update in 1 step — i.e., if an element is not greater than current max, then it terminates. So if the first element is not $ n $, and the second is not greater than first, then it terminates. But if $ n $ is not first, and the second element is smaller than first, then it terminates at position 2, returning first element < n. So many failures. But our formula still holds. So final answer: Let $ \text{mod} = 10^9 + 7 $. If $ k \geq n $, output $ 0 $. Else, compute: $$ \sum_{p = k+1}^{n} (p - k) \cdot (p - 2)! \cdot (n - p)! \mod \text{mod} $$ We can precompute factorials up to $ 10^6 $, and compute the sum efficiently. Note: $ (p - 2)! \cdot (n - p)! $ is the product of two factorials, and we multiply by $ (p - k) $. We can write: Let $ f(p) = (p - k) \cdot (p - 2)! \cdot (n - p)! $ Then answer = $ \sum_{p=k+1}^{n} f(p) $ This is computable in $ O(n) $ with precomputed factorials. --- ### Final Formal Answer: Let $ n, k \in \mathbb{N} $, $ 1 \leq n, k \leq 10^6 $. Define the set of permutations $ \pi \in S_n $ for which the function returns a value $ \ne n $. The number of such permutations is: $$ \begin{cases} \displaystyle \sum_{p = k+1}^{n} (p - k) \cdot (p - 2)! \cdot (n - p)! \mod (10^9 + 7), & \text{if } k < n \\ 0, & \text{if } k \geq n \end{cases} $$