[Codeforces Round #445][Codeforces 886E]Maximum Element

    题意：有一个寻找一个n排列中最大数的算法如下（太难描述了QAQ）

int fast_max(int n, int a[]) { 
    int ans = 0;
    int offset = 0;
    for (int i = 0; i < n; ++i)
        if (ans < a[i]) {
            ans = a[i];
            offset = 0;
        } else {
            offset = offset + 1;
            if (offset == k)
                return ans;
        }
    return ans;
}

    求使这个算法错误（即ans不等于n）的n排列的数目。

    题解：我翻译一下评论区里的回答，那个比较详细。

        首先设\(D(n)\)表示长度为n的，且\(p_n=n\)（排列的第n个数为n）的满足条件的排序。

        先给出答案的形式：\[D(n)=(n-k-1)\cdot(n-2)!+\sum_{h=n-k}^{n-1}D(h)\cdot\frac{(n-2)!}{(h-1)!}\]

        第一项表示当n-1这个数的位置在1到n-k-1之间时的排列数，显然此时所有的排列都是符合条件的。数n-1有\(n-k-1\)个位置可以放，其余n-2个数有\((n-2)!\)个位置可以放。

        第二项表示当n-1这个数的位置在n-k到n-1之间时满足条件的排列数。设n-1的位置为h，显然，如果程序访问到了h，那么它接下来一定能访问到n，这个排列就一定是不符合条件的。要使排列满足条件，则需要使程序在h之前就停下来，即前h-1个数是符合条件的。如果我们确定下来了前h-1个数，那么这样的排列数为\(D(h)\cdot(n-h-1)!\)，因为在数n与数n-1之间的(n-h-1)个数可以任意排列。前h-1个数有\(C_{n-2}^{h-1}\)种选择方案。

        相乘得当n-1的位置为h时的方案数为\[D(h)\cdot(n-h-1)!\cdot\frac{(n-2)!}{(h-1)!(n-h-1)!}=D(h)\cdot\frac{(n-2)!}{(h-1)!}=(n-2)!\frac{D(h)}{(h-1)!}\]

        其中\(\frac{D(h)}{(h-1)!}\)可以通过记录和来处理。

        为了得到最终答案，我们还要算出数n出现在排列中的每个位置的方案数。设数n的位置为i，那么这样的排列数为确定前i-1个数后D(i)（数n不能到达，所以前i个数满足条件即可）乘上后n-i个数任意排列的方案数，即\(D(i)\cdot C_{n-1}^{i-1}\cdot(n-i)!=D(i)\cdot\frac{(n-1)!}{(i-1)!}\)。答案求和即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,mo=1e9+7;

int Pow(int x,int p)
{
	long long xx=x,res=1;
	while (p)
	{
		if (p&1) res=res*xx%mo;
		xx=xx*xx%mo;
		p>>=1;
	}
	return (int)res;
}

int inv(int x) {return Pow(x,mo-2);}

long long kt[maxn];
long long f[maxn];
int n,k,ans;

int main()
{
	kt[0]=1;
	for (int i=1;i<=1000000;i++) kt[i]=kt[i-1]*i%mo;
	scanf("%d%d",&n,&k);
	if (k+1>=n)
	{
		puts("0");
		return 0;
	}
	for (int i=k+2;i<=n;i++)
	{
		static long long sum=0;
		f[i]=kt[i-2]*(i-k-1)%mo;
		f[i]=(f[i]+sum*kt[i-2]%mo)%mo;
		sum=(sum+f[i]*inv(kt[i-1])%mo)%mo;
		if (i-k>=k+2) sum=(sum-f[i-k]*inv(kt[i-k-1])%mo+mo)%mo;
	}
	for (int i=k+2;i<=n;i++)
	{
		ans=(ans+f[i]*kt[n-1]%mo*inv(kt[i-1])%mo)%mo;
	}
	printf("%d\n",ans);
	return 0;
}