自动搬运

查看原文

来自洛谷，原作者为

	λᴉʍ 大家好，我是刚学OI的萌新

搬运于2025-08-24 22:08:14，当前版本为作者最后更新于2019-02-27 16:38:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

毒毒题，对着嘤文题解看了贼久

首先考虑此题的一个弱化版本：如果输入的所有$c_i$相等怎么做

现在假设有$len$个数，取值从$v$到$10^9$，而且每连续$k$个数至少有一个是$v$

那么取值就只有$v$和$>v$两种取值了，$>v$的取值有$10^9-v$种，设为$x$

那么有一个显然的dp，$f_i$表示这个问题i个数的答案

枚举这个数列的最后一个取值为$v$的数，假设是第$j$个，那么后面的$i-j$个数有$x$种选法

$f_i=\sum_{j=i-k+1}^{i}x^{i-j}f_{j-1}$

这个dp显然是不行的，还有一个dp，也是设$f_i$表示这个问题i个数的答案

$f_i=(x+1)f_{i-1}-x^kf_{i-k-1}$

第$i$个数随便选，乘$i-1$个数的答案，这时可能出现问题，就是第$i-k+1$个数到第$i$个数都$>v$导致了不合法，所以要减掉这些情况

为什么减掉的是$x^kf_{i-k-1}$呢，显然这$k$个数的放法共$x^k$种没有问题，要注意一下从第$i-k+1$个数到第$i-1$个数都$>v$，那么只有第$i-k$个数取值是$v$才能够满足最小值的条件，所以前面的取值方案数是$f_{i-k-1}$

il int solve(int v,int len){
	int x=1000000000-v,xk=pow(x,k);
	f[0]=f[1]=1;
	for(int i=2;i<=len+1;++i){
		f[i]=1ll*(x+1)*f[i-1]%mod;
		if(i-k-1>=0)f[i]=(f[i]-1ll*xk*f[i-k-1]%mod+mod)%mod;
	}
	return f[len+1];
}

那么解决了前面的问题，后面的也很好办

设$s(v,len)$表示现在假设有$len$个数，取值从$v$到$10^9$，而且每连续$k$个数至少有一个是$v$问题的答案，可以在$O(len)$时间内球解

首先，可以将一段相等的$c$合并起来

然后（开始口胡）

对于一个段$c_i=\cdots=c_j$，如果只有这一段，方案数为$s(c_i,j-i+k)$

如果有一个$c_{i-1}>c_i$

那么可以知道的是

$\min\{a_{i-1},\cdots,a_{i+k-2}\}=c_{i-1}$

这里可以推出$a_{i-1},\cdots,a_{i+k-2}\geq c_{i-1}$

$\min\{a_{i},\cdots,a_{i+k-1}\}=c_{i}$

前面已经推出$a_{i},\cdots,a_{i+k-2}\geq c_{i-1}>c_{i}$了，所以这些都不可能是最小值

这一段的最小值只能有一个就是$a_{i+k-1}=c_{i}$

前面的数也都在前一段的范围内

所以这一段最前面$k$个数就没了，其中前$k-1$个数会在前面段计算答案，第$k$个数只有一个取值$c_i$

对于后面也同理，如果$c_{j+1}>c_j$则后面$k$个数没了

所以一段的len实际上是$j-i+k$减去0到2个$k$

对于所有的段依次球解最后方案数乘起来即可

代码极为简单

#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 1000000007
typedef long long ll;
il ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int n,k;
int a[100010];
int f[100010];
il int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
il int solve(int v,int len){
	int x=1000000000-v,xk=pow(x,k);
	f[0]=f[1]=1;
	for(int i=2;i<=len+1;++i){
		f[i]=1ll*(x+1)*f[i-1]%mod;
		if(i-k-1>=0)f[i]=(f[i]-1ll*xk*f[i-k-1]%mod+mod)%mod;
	}
	return f[len+1];
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	n=gi(),k=gi();
	for(int i=1;i<=n-k+1;++i)a[i]=gi();
	int ans=1,len;
	for(int i=1,j;i<=n-k+1;i=j+1){
		j=i;
		while(a[j+1]==a[i])++j;
		len=j-i+k;
		if(i!=1&&a[i-1]>a[i])len-=k;
		if(j!=n-k+1&&a[j+1]>a[i])len-=k;
		if(len>0)ans=1ll*ans*solve(a[i],len)%mod;
	}
	printf("%d\n",ans);
	return 0;
}