题目大意

给你 $n$ 和 $m$ 且一共有 $n-m+1$ 组数据。第 $i$ 组数据代表 $\min\{\sum_{i=i+m-1}^{i}val_{i}\}$ 然后让你求符合要求的方案数。

题意分析

这时我们可以由它的性质，即第 $i$ 组数据代表 $\min\{\sum_{i=i+m-1}^{i}val_{i}\}$ 来思考，可以发现：

1. 两个相同且相邻的区间的方案数与他们共同的 $V$ 值有关，即设 $V= \min\{\sum_{i=i+m-1}^{i}val_{i}\}=val_i=val_{i+1}$ 为 $V$ 的值，接着用递推直接求，时间复杂度是 $O(n^2)$ 的,但可以用数学方法变成 $O(n)$ 的时间复杂度。
2. 如果我们发现两个不相等但相邻的区间，我们就可以发现这时就可以固定住一个数，而这个数的值则听 $S=\max\{val_{i},val_{i+1}\}$ 接着推出就行了。

具体可参考代码理解。

CODE

#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define int long long
#define ull unsigned long long
#define ri register int
#define mod 1000000007
#define N 100005
using namespace std;
const int INF=1e9;
int n,m,jk,ans,num,cnt,tot;
int dis[N],vis[N],wis[N],f[N];

void read(int &x){//快读
	x=0;int ff=1;char ty;
	ty=getchar();
	while(!(ty>='0'&&ty<='9')){
		if(ty=='-') ff=-1;ty=getchar();
	}
	while(ty>='0'&&ty<='9')
		x=(x<<3)+(x<<1)+ty-'0',ty=getchar();
	x*=ff;return;
}

void write(int x){//快输
	if(x<0){x=-x;putchar('-');}
	if(x>=10) write(x/10);putchar('0'+x%10);
	return;
}

int ksm(int a,int b)
{
	int result=1;
	while(b>0){
		if(b&1) result=result*a%mod;
		a*=a;b>>=1;a%=mod;
	}
	return result%mod;
}
signed main(){
//	freopen("tracking2.in","r",stdin);
//	freopen("tracking2.out","w",stdout);
	read(n);read(m);ans=1;int i1=1,j=1;
	for(int i=1;i<=n-m+1;i++) read(dis[i]);
	while(j<=n-m+1)
	{
		while(dis[i1]==dis[j]&&j<=n-m+1) j++;
		j--;int len=j-i1+m;
		if(i1>1&&dis[i1-1]>dis[i1]) len-=m;
		if(j<n-m+1&&dis[j+1]>dis[j]) len-=m;
		f[0]=f[1]=1;int sum=ksm(INF-dis[i1],m)%mod;
		for(int i=2;i<=len+1;i++)//判断贡献
		{
			f[i]=(INF-dis[i1]+1)%mod*f[i-1]%mod;
			f[i]<0?f[i]+=mod:0;f[i]%=mod;
			if(i-m-1>=0) f[i]=f[i]-sum*f[i-m-1]%mod;
			f[i]<0?f[i]+=mod:0;f[i]%=mod;
		}
		if(len>0) ans=ans*f[len+1]%mod;ans%=mod;
		i1=j+1;j++;
	}
//	for(int i=1;i<=n;i++) wk(f[i]);
	wh(ans);
	return 0;
}