题目传送门CF886E
洛谷入口
题目大意
(有个神仙写了个序列求max，它长下面这样：)
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;
}
(现在他比较关心的是出错的情况，请你算出有多少个1～n的排列在这个函数的计算下答案不为n)
(最终结果对10^9+7取模)
数据范围
(circ) (n,kle10^6)
题解
这题应该可以较为轻易地看出这要用DP
题意要运算不正确序列的方案数
那只要求出运算正确的方案数
再用(n!)去减他就好了
那先定状态为(f_i)为到第i位时运算正确的方案数
那么会出来一个状态转移方程：
(f_i=sumlimits_{j=i-k+1}^{i}A^{i-j}_{i-1} imes f_{j-1})
意思就是对于f_i来说
假设这i个数最大的i在第j位上
那么在第j位后面距第i个有i-j个位置
而有i-1个数可供选择填
所以就有了(C^{i-j}_{i-1})这项的存在
那个((i-j)!)意思就是把挑出来的这(i-j)个进行随便排
f_{j-1}就是j之前的方案数这就不多说了
当然为了满足只看k个的情况，需要注意j的枚举范围
相信也可以理解了，最早只能在i-k+1，这样就能不重不漏地枚举了
那么为了不超时成(O(nk))，下面开始化简（推式子）
（高能部分开始↓↓）
以下推式子可能会出现手误or脑子短路，望发现者在评论区纠正一下，谢谢！
(f_i=sumlimits_{j=i-k+1}^{i}A^{i-j}_{i-1} imes f_{j-1})
(=sumlimits_{j=i-k+1}^ifrac{(i-1)!}{[(i-1)-(i-j)]!} imes f_{j-1})
(=sumlimits_{j=i-k+1}^ifrac{(i-1)!}{[(j-1)!} imes f_{j-1})
(=sumlimits_{j=i-k+1}^i(i-1)! imesfrac{f_{j-1}}{(j-1)!})
把j往前推一可得：
(f_i=(i-1)! imessumlimits_{j=i-k}^{i-1}frac{f_j}{j!})
所以这样就好多了
那只要维护一下(frac{f_j}{j!})的前缀和就可以线性求出所有f_i的值了！
最后最终答案就按照刚才的道理：
(n!-sumlimits^n_{i=1}A^{n-i}_{n-1} imes f_{n-1})
(=n!-(n-1)! imessumlimits^{n-1}_{i=0}frac{f_i}{i})
这就是个前缀和后(O(1))可以解决的东西了
那么预处理上需要所有(iin[1,n])的阶乘和阶乘的逆元
用个递推就好，加个对(frac{f_i}{i})的前缀和，还有个快速幂
这题就没问题了！
（也看得出来这题的代码量很小）
下面，上代码！↓↓↓
AC代码
#include<bits/stdc++.h>
#define int long long//粗暴的方法
using namespace std;
int f[1000010],g[1000010],sum[1000010],inv[1000010],n,k,th[1000010],mod=1e9+7;;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int ksm(int x,int y){
int tot=1,tmp=x;
while(y){
if(y&1)tot=tot*tmp%mod;
tmp=tmp*tmp%mod;
y>>=1;
}
return tot;
}
signed main(){
n=read();k=read();
th[0]=1;f[0]=1;sum[0]=1;
for(int i=1;i<=n;i++)th[i]=th[i-1]*i%mod;
inv[n]=ksm(th[n],mod-2);
for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++){
f[i]=th[i-1]*(sum[i-1]-sum[max(i-k,1LL*0)-1])%mod;
g[i]=f[i]*inv[i]%mod;
sum[i]=(sum[i-1]+g[i])%mod;
}
int ans=th[n-1]*sum[n-1]%mod;
cout<<(th[n]-ans+mod)%mod;
}