题目链接：
题意：
给你 \(n\)和 \(k\)。
让你找一种全排列长度为\(n\)的 \(p\)，满足存在下标 \(i\)，\(p_i\)大于所有 \(p_j\)，\(j\epsilon[1,i-1]\)同时大于所有\(p_i\)，\(j\epsilon[i+1,i+k]\)。问你满足这样条件的排列有多少种？
题解：
设\(dp[i]\)表示以 \(i\) 结尾的，满足题目要求的\(1\) ~ \(i\)排列。
显然。
如果，\(i<=k+1\)，则\(dp[i]=0\)。
因为我们考虑 \(i-1\) 在这个排列当中的位置。当 \(i-1\) 和 \(i\) 之间的数字超过 \(k\)个时，显然成立，此时共有 \((i-k-1)*(i-2)!\) 种序列。
否则，\(i-1\) 的下标\(j >= i-k\), 把排列的前 \(j\) 个数字离散化为都由\(1\) ~ \(j\) 组合之后，这些数字组成的排列一定是以 \(j\) 结尾，满足题目要求的排列，共有\(dp[j]\)个，因为后面的数字少于 \(k\)个，不可能满足题目要求。\(dp[j]\) 是离散化之后的结果，离散化之前的结果共有\(dp[j]*C(i-2,j-1)*(i-j-1)!=dp[j]*\frac{(i-2)!}{(j-1)!}\)个。可以理解为：先在剩下的 \(i-2\) 个数当中取 \(j-1\) 个排在下标为$ 1~j-1的$位置，下标 \(j\) 之后到最后一个元素之前的位置随意排列)。
所以,两种情况加起来就是：
\(dp[i]=(i-k-1)*(i-2)!+\sum_{j=i-k}^{i-1}dp[j]*\frac{(i-2)!}{(j-1)!}\)。
但是这样直接计算要 \(O(n^2)\)。
提取一下\((i-2)!\)，变成：
\(dp[i]=(i-k-1)*(i-2)!+(i-2)!*\sum_{j=i-k}^{i-1}\frac{dp[j]}{(j-1)!}\)
\(= (i-2)!*[(i-k-1)+\sum_{j=i-k}^{i-1}\frac{dp[j]}{(j-1)!}]\)
后面一项 \(\frac{dp[j]}{(j-1)!}\) 就可以利用前缀和求出。阶乘的乘除可以利用逆元求出。直接算就是O(n)。
\(dp[n]\)是以 \(n\) 结尾的排列个数。我们把 \(n\) 排在不同的位置 \(h\)，把\(n\)下标之前的数离散化到\(1\) ~ \(h-1\)，跟上面的一样，所以最终答案为:
\(\sum_{h=1}^{n}dp[h]*\frac{(n-1)!}{(h-1)!}\)。
总复杂度：\(O(n)\)
代码：
#includeusing namespace std;typedef long long ll;const int maxn = 1000010;ll inv[maxn],fac[maxn],dp[maxn],sum[maxn];const int mod =1e9+7;ll qpower(ll a,ll b){ ll res = 1; while(b) { if(b&1)res = res*a%mod; b>>=1; a= a*a%mod; } return res;}int main(int argc, char const *argv[]) { ll n,k; ll ans = 0; cin>>n>>k; if(k+1>=n){ printf("0\n"); exit(0); } fac[0] = 1; for (int i = 1; i <=n; i++) { fac[i] = (fac[i-1] * i) %mod; } inv[n] = qpower(fac[n],mod-2); for(int i=n-1;i>=0;i--){ inv[i] = inv[i+1] *(i+1); inv[i] %= mod; } memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); for(int i=k+2;i<=n;i++){ dp[i] = (i-k-1 + (sum[i-1] - sum[i-k-1] +mod)%mod)%mod; dp[i] = (dp[i] * fac[i-2]) % mod; sum[i] = sum[i-1] + (dp[i] * inv[i-1])%mod; sum[i] %= mod; ans += (((dp[i] * fac[n-1]) % mod) * inv[i-1])%mod; ans %= mod; } cout< <
ADDITION：
当然也可以把不符合题目条件的先算出来，然后用 \(n!\)减去不符合条件的个数，即为答案。
代码：
#includeusing namespace std;typedef long long ll;const int maxn = 1000005;ll inv[maxn],fac[maxn],dp[maxn],sum[maxn];const int mod =1e9+7;ll qpower(ll a,ll b){ ll res = 1; while(b) { if(b&1)res = res*a%mod; b>>=1; a= a*a%mod; } return res;}int main(int argc, char const *argv[]) { ll n,k; cin>>n>>k; if(k+1>=n) { printf("0\n"); exit(0); } fac[0] = 1; for(int i=1;i<=n;i++){ fac[i] = fac[i-1]*i%mod; } inv[n] = qpower(fac[n],mod-2); for(int i=n-1;i>=0;i--){ inv[i] = inv[i+1] * (i+1) %mod; } dp[1] = sum[1] = 1; ll ans = fac[n-1]; for(int i=2;i<=n;i++){ dp[i] = (sum[i-1] - sum[max(0LL,i-k-1)]) *fac[i-2] %mod; sum[i] = (sum[i-1] + dp[i] * inv[i-1]) % mod; ans = (ans + dp[i] * fac[n-1] %mod * inv[i-1])%mod; } cout<<(fac[n]-ans+mod)%mod<