CF886E Maximum Element

Description

​ 有一个排列 $a_1, a_2,\cdots, a_n$。已知一种求最大值的方式：遍历一遍序列，如果一个数比他后面的 $k$ 个值都要大，则直接返回该值。求有多少个排列使得这种方式返回的答案是错误的。

​ $n, k \leq 10^6$ 。

Solution

​ 考虑如何求正确的排列个数。可以发现，如果一个序列在求最大值时还没有遍历到 $n$ 就中途退出了，那么他返回的一定不会是正确的值。

​ 于是可以设计出 $dp$ 状态：$dp_i$ 表示遍历完前 $i$ 个数依然没有返回的 $1,2,\cdots, i$ 的排列个数 。

​ 注意，这里只考虑 $1, 2, \cdots, i$ 的排列个数，即他们的相对大小关系。

​ 转移时，我们可以枚举前 $i - 1$ 个数的最大值所在的位置 $j$。显然有几个性质。一是 $j$ 要在 $[i - k + 1, i]$ 内，否则就会退出；二是在遍历到这个最大值之前不能退出；三是这个最大值之后的 $i - j$ 个位置可以随便交换位置，原因是他们不会对退出这件事造成任何影响。

​ 于是，我们可以列出转移方程：

$$dp_i = \sum\limits_{j=i-k+1}^{i} \binom{i-1}{j-1} \cdot dp_{j-1} \cdot (i-j)!$$

​ 暴力 dp 是 $O(n^2)$ 的，考虑把组合数拆开，简单推导可得：

$$dp_i = (i-1)!\cdot \sum\limits_{j=i-k}^{i-1} \frac{dp_j}{j!}$$

​ 直接维护 $\sum\limits_{j=i-k}^{i-1} \frac{dp_j}{j!}$ 即可。

​ 最后的答案如何计算？考虑最大值的位置 $i​$ ，有：

$$\begin{aligned} ans &= n!- \sum\limits_{i=1}^{n} dp_{i-1} \cdot \binom{n-1}{i-1} \cdot (n-i)! \\ &= n!-(n-1)!\cdot \sum\limits_{i=1}^{n} \frac{dp_{i-1}}{(i-1)!} \end{aligned}$$

​ 时间复杂度 $O(n)$。

Code

代码中可以考虑直接维护 $\frac{dp_i}{i!}$

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e6 + 10; 
const int mod = 1000000007;


int n, k, f[N], g[N], dp[N]; 

int add(int x, int y) {
  return (x += y) >= mod ? x - mod : x; 
}

int fpw(int x, int k, int p) {
  int ret = 1; 
  while(k) {
    if(k & 1) ret = 1ll * ret * x % p; 
    x = 1ll * x * x % p; k >>= 1; 
  } return ret; 
}

int main() {
  scanf("%d %d", &n, &k); 
  f[0] = 1; 
  for(int i = 1; i <= n; i++) 
    f[i] = 1ll * f[i - 1] * i % mod; 
  g[n] = fpw(f[n], mod - 2, mod);
  for(int i = n - 1; i >= 0; i--) 
    g[i] = 1ll * g[i + 1] * (i + 1) % mod;  
  int s = 0; dp[0] = 1; 
  for(int i = 1; i <= n; i++) {
    s = add(s, dp[i - 1]); 
    if(i > k) s = add(s, mod - dp[i - k - 1]);
    dp[i] = 1ll * g[i] * f[i - 1] % mod * s % mod;  
  } s = 0; 
  for(int i = 1; i <= n; i++) s = add(s, dp[i - 1]); 
  printf("%lld\n", 1ll * f[n - 1] * add(n, mod - s) % mod); 
  return 0; 
}