题目链接：https://codeforces.com/contest/1809/problem/G
题解：
一道很强的 dp
首先翻译条件：predictable 是什么意思？发现就是对每一个下标，前缀 max 和下一个位置至少差一个 \(k+1\)
看到 \(n \leq 10^6\)，可以猜测最后应该是线性的，考虑线性 dp
设 \(dp[i]\) 表示已经选了前 \(i\) 大 rating 的人，并且第一个位置填的数不能和剩下没选的人冲突，这里“冲突”指的是 \(|x-y| \leq k\)
为什么要这么设状态？因为我们不可能再设一维状态来表示前缀 max，因此我们需要确保每一次转移的时候都转移到合法状态
假设现在已经填了前 \(i\) 大的数，那么第 \(i+1\) 个数有以下两种填法：
- 填在第 \(1\cdots i\) 个数的后面，那么显然这个状态一定合法（开头的数没有变），转移为 \(dp[i+1] \leftarrow dp[i]\times i\)
- 填在第 \(1\) 个数前面（即放在开头），那么和当前数冲突的数字（必然是 \(i+2 \cdots to[i]-1\) 连续的一段）应该也一块放，这样保证状态还是合法的。考虑先放第 \(i+2\)，有 \(i\) 种方法（放在第 \(1\cdots i\) 的后面），再放 \(i+3\)，有 \(i+1\) 种……最后再放开头的 \(i+1\)，转移为 \(dp[to[i+1]-1] \leftarrow dp[i]\times (i \times \cdots \times to[i+1]-3)\)
代码：
// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 1e6+5, mod = 998244353;
int n,k,a[maxn],dp[maxn];
int fac[maxn], inv[maxn], to[maxn];
int pw(int x,int y){
if(!y)return 1;
if(y==1)return x;
int mid=pw(x,y>>1);
if(y&1)return 1ll*mid*mid%mod*x%mod;
return 1ll*mid*mid%mod;
}
int que(int l,int r){
return 1ll*fac[r]*inv[l-1]%mod;
}
signed main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
reverse(a+1,a+n+1);
for(int i=1, j=1;i<=n;i++){
while(j <= n && a[i] - a[j] <= k)++ j;
to[i] = j;
}
fac[0] = inv[0] = 1;
for(int i=1;i<=n;i++)fac[i] = 1ll*fac[i-1]*i%mod;
inv[n] = pw(fac[n], mod-2);
for(int i=n-1;i>=1;i--)inv[i] = 1ll*inv[i+1]*(i+1)%mod;
if(a[1] - a[2] > k)dp[1] = 1;
for(int i=1;i<n;i++){
// (i+2) .. (to[i]-1)
// if(to[i+1]-1 > i+1)
(dp[to[i+1]-1] += 1ll*dp[i]*que(i, to[i+1]-3)%mod) %= mod;
(dp[i+1] += 1ll*dp[i]*i%mod) %= mod;
}
printf("%d\n",dp[n]);
return 0;
}