考虑正难则反,答案即为\(n!-\text{返回值为n的排列数}\)
一个排列的返回值为\(n\),当且仅当在\(n\)出现之前没有一个数后面有连续\(k\)个小于它的数
设\(f_i\)表示\(1\)到\(i\)的排列中,没有任何一个数后面有连续\(k\)个小于它的数
枚举\(i\)的位置,则有
\[f_i=\sum_{j=1}^kA_{i-1}^{j-1}f_{i-j}\]
即把\(i\)放在倒数第\(j\)个位置,从\(1\)到\(i-1\)中选\(j-1\)个数排列在\(i\)后面,剩下\(i-j\)个个数放在\(i\)前面并且保证合法
把排列数打开,就变成了\(f_i=(i-1)!\sum_{j=1}^{k}\frac{f_{i-j}}{(i-j)!}\)
维护一下\(\frac{f_i}{i!}\)的前缀和就可以快速转移了
枚举一下\(n\)所在的位置,返回值为\(n\)的排列数即为
\[\sum_{i=1}^nf_{i-1}\binom{n-1}{i-1}(n-i)!\]
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=1e9+7;
const int maxn=1e6+5;
int pre[maxn],fac[maxn],ifac[maxn],inv[maxn],f[maxn];
int n,m;
inline int C(int n,int m) {
if(n<m) return 0;
return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int dqm(int x) {return x<0?x+mod:x;}
inline int calc(int l,int r) {
if(l<=0) return pre[r];
return dqm(pre[r]-pre[l-1]);
}
int main() {
n=read(),m=read();fac[0]=ifac[0]=inv[1]=1;
for(re int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
for(re int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(re int i=1;i<=n;i++) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
f[0]=1;pre[0]=1;
for(re int i=1;i<n;i++) {
f[i]=1ll*calc(i-m,i-1)*fac[i-1]%mod;
pre[i]=qm(pre[i-1]+1ll*f[i]*ifac[i]%mod);
}
int ans=0;
for(re int i=1;i<=n;i++)
ans=qm(ans+1ll*f[i-1]*C(n-1,i-1)%mod*fac[n-i]%mod);
printf("%d\n",dqm(fac[n]-ans));
return 0;
}