- 有一个值域为([1,10^9])的整数序列，给出每相邻(k)个元素中的最小值，求原序列可能的个数。
- (nle10^5)
(a_i)全相同时的(DP)
方便起见记(w=10^9-a_i)。
那也就是说，至多隔(k)个位置选择一次(a_i)，而不选(a_i)的时候有(w)种选法。
因此设(f_i)表示第(i)个位置选择了的方案数，得出暴力转移式：
[f_i=sum_{j=i-k}^{i-1}f_j imes w^{i-j-1}
]
我们发现转移的系数是(w^{i-j-1})，因此考虑把(f_{i-1})乘上(w)，发现：
[f_{i-1} imes w=sum_{j=i-k-1}^{i-2}f_j imes w^{i-j-1}
]
它和(f_i)只有(f_{i-k-1})和(f_{i-1})两项不同，稍微补正一下即可：
[f_i=f_{i-1} imes (w+1)-f_{i-k-1} imes w^k
]
这样就可以(O(n))去(DP)了。
(a_i)不相同时的分段拆解
对于(a_i)全相同的一段([i,j])，粗略考虑它在原序列中管辖的区间为([i,j+k-1])，长度为(j-i+k)。
但是，如果(a_{i-1}>a_i)，说明(s_{i+k-1}=a_i)，且(s_{isim i+k-2})肯定全都大于等于(a_{i-1})，因此当前段管辖区间大小减少(k)。
同理，如果(a_{j+1}>a_i)，说明(s_j=a_i)，且(s_{j+1sim j+k-1})肯定全都大于等于(a_{j+1})，因此当前段管辖区间大小减少(k)。
然后发现不同的管辖区间之间是独立的，分别按照前面的方法(DP)然后把方案数相乘即可。
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define INF 1000000000
#define X 1000000007
using namespace std;
int n,k,a[N+5];I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int f[N+5];I int DP(CI x,CI n)//动态规划
{
RI i,w=INF-x,p=QP(w,k);f[0]=f[1]=1;//初始化
for(i=2;i<=n+1;++i) f[i]=(1LL*f[i-1]*(w+1)-(i>k?1LL*f[i-k-1]*p%X:0)+X)%X;return f[n+1];//利用f[i-1]*w高效转移
}
int main()
{
RI i,j,p;for(scanf("%d%d",&n,&k),i=1;i<=n-k+1;++i) scanf("%d",a+i);
RI t=1,o;for(i=1;i<=n-k+1;i=j+1) {j=i;W(a[j+1]==a[i]) ++j;o=j-i+k-(a[i-1]>a[i])*k-(a[j+1]>a[i])*k,t=1LL*t*DP(a[i],o)%X;}//根据a[i]分段拆解
return printf("%d
",t),0;
}