description
给定 \(n,k\)，求有多少个 \(n\) 的排列满足 \(\forall i\in[k+1,n],\min\limits_{j=i-k}^{i-1} a_j < a_i\)。
- \(n,k\leq 10^7\)
solution
设 \(f_i\) 表示对于给定的 \(k\)，排列长度为 \(i\) 时的答案。
转移时，我们考虑在头部添加新的数，设添加后的序列是 \(\{a\}\)。根据限制，我们只需考虑新加的数能不能使 \(a_{k+1}\) 大于它前面最小的数。
我们再来考虑一个性质：对于一个合法的排列，排列中的最小数一定在前 \(k\) 个数中。
于是，讨论 \(a_{k+1}\) 是否等于第 \(2\) 到第 \(i\) 个数的最小数。
-
如果是，那么只有 \(a_1\) 也就是新添加的数为当前整个序列的最小数时才合法。此时第 \(2\) 到第 \(k\) 个数可以填除整个序列最小次小外任意的数。方案数就可以从 \(f_{i-k-1}\) 乘上系数转移过来了。
-
否则，那么后面 \(i-1\) 个数的最小数一定在第 \(2\) 到第 \(k\) 个位置，方案数就是 \(f_{i-1}\) 减去后 \(i-1\) 个数的最小数在第 \(k+1\) 个位置的方案数，在第一种情况中已经说明了计算方法。头部新添加的数是可以任意填的，所以还要乘上系数 \(i\)。
综上，我们有转移：
-
\(f_{i}=i!,0\leq i\leq k\)
-
\(f_{i}=(f_{i-1}-f_{i-k-1}\times A_{k-1}^{i-2})\times i+f_{i-k-1}\times A_{k-1}^{i-2}\)
预处理阶乘和阶乘逆元，时间复杂度 \(O(n)\)。
code
/******
*zz *
*af *
*an *
*ti *
******/
#include<bits/stdc++.h>
using namespace std;
using E=long long;
using ui=uint32_t;
constexpr E inf=1e16,mod=998244353;
vector<E> fac,ifac;
E n,k;
inline E ksm(E a,E b){
E ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
inline E C(E n,E m){
if(n<0||m<0) return 0;
return n<m?0:fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
int main(){
cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
fac.resize(n+1),ifac.resize(n+1);
fac[0]=ifac[0]=1;
for(int i=1; i<=n; i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1; i; i--) ifac[i]=ifac[i+1]*(i+1)%mod;
vector<E> f(n+1);
for(int i=0; i<=k; i++) f[i]=fac[i];
for(int i=k+1; i<=n; i++){
f[i]=((f[i-1]-f[i-k-1]*fac[k-1]%mod*C(i-2,k-1)%mod+mod)%mod*i+fac[k-1]*f[i-k-1]%mod*C(i-2,k-1)%mod)%mod;
}
cout<<f[n];
return 0;
}