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

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

那么取值就只有 \(v\) 和 \(>v\) 两种取值了，\(>v\) 的取值有\(1^09−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，也是设fi表示这个问题 \(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}

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=⋯=c_j\)，如果只有这一段，方案数为 \(s(c_i,j−i+k)\)

如果有一个 \(c_{i−1}>c_i\)

那么可以知道的是: \(min{a_{i−1},⋯,a_{i+k−2}}=c_{i−1}\)

这里可以推出 \(a_{i−1},⋯,a_{i+k−2} ≥ c_{i−1}\)

\(min{a_i,⋯,a_{i+k−1}}=c_i\)

前面已经推出 \(a_i,⋯,a_{i+k−2} ≥ 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\)

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