tag:dp，组合计数
经典看完dp定义秒懂
考虑算出满足条件的再用总数减。若一个排列满足条件，那么就不能在遇到 \(a_i=n\) 之前返回。所以只需要考虑 \(a_i=n\) 前面的部分。
为什么使用dp？若一个排列扫完之后没有返回，那么单独把这个排列的任何一段区间拿出来扫，都不会返回，并且拿出来的这个区间可以看作一个 \([1,len]\) 的排列。设 \(f_i\) 为长度为 \(i\) 的满足条件的排列个数。
那么答案就是：
\[ans=\sum_{i=1}^nf_{i-1}\binom {n-1}{n-i}(n-i)! \]枚举 \(n\) 所在位置 \(i\)，\([1,i-1]\) 的方案为 \(f_{i-1}\)，\([i+1,n]\) 的方案为 \((n-i)!\)，选数的方案为 \(\binom{n-1}{n-i}\)。
考虑转移，要使得递归到子问题时，这个子问题只与区间长度有关系。考虑枚举 \(mx\) 的位置，因为扫完排列后没有返回，所以 \(mx\) 的位置一定在 \([len-k,len]\)，于是就可以递归下去了。
\[f_x = \sum_{i=x-k}^xf_{i-1}\binom{x-1}{x-i}(x-i)! \]枚举 \(mx\) 的位置 \(i\)，\([1,i-1]\) 为 \(f_{i-1}\)，\([i+1,len]\) 为 \((x-i)!\)，选数为 \(\binom{x-1}{x-i}\)。
简单化简一下：
\[f_x=(x-1)!\sum_{i=x-k-1}^{x-1}\frac{f_{i-1}}{(i-1)!} \]和式部分可以直接用一个 \(sum\) 变量维护着走（去头添尾），于是复杂度 \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void Read(T &n){
char ch; bool flag=false;
while(!isdigit(ch=getchar())){if(ch=='-')flag=true;}
for(n=ch^48; isdigit(ch=getchar()); n=(n<<1)+(n<<3)+(ch^48));
if(flag) n=-n;
}
enum{
MAXN = 1000005,
MOD = 1000000007
};
inline int dec(int a, int b){
a -= b;
if(a<0) a += MOD;
return a;
}
inline void ddec(int &a, int b){a = dec(a,b);}
int n, k;
int f[MAXN], sum, inv[MAXN], jc[MAXN], ans;
inline int C(int n, int m){return 1ll*jc[n]*inv[m]%MOD*inv[n-m]%MOD;}
int main(){
Read(n); Read(k);
inv[1] = 1; for(register int i=2; i<=n; i++) inv[i] = 1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
inv[0] = 1; for(register int i=2; i<=n; i++) inv[i] = 1ll*inv[i]*inv[i-1]%MOD;
jc[0] = 1; for(register int i=1; i<=n; i++) jc[i] = 1ll*jc[i-1]*i%MOD;
sum = 1; f[0] = 1;
for(register int i=1; i<=n; i++){
f[i] = 1ll*sum*jc[i-1]%MOD;
if(i-k>=0) ddec(sum,1ll*f[i-k]*inv[i-k]%MOD);
sum = (sum+1ll*f[i]*inv[i])%MOD;
ans = (ans+1ll*f[i-1]*C(n-1,n-i)%MOD*jc[n-i])%MOD;
}
cout<<dec(jc[n],ans)<<endl;
return 0;
}