题解 P5204 【[USACO19JAN]Train Tracking 2】
PhantasmDragon
·
·
题解
这道题好神仙啊...
简要题意:给你一个长度为 n 的数列 a 的 n-k+1 个长度为 k 的子区间的最小值 c_i, 即 c_x=\min_{i=x}^{i\leq x+k-1}
a_i, 求有几种满足给出 c 序列的 a 序列.
拿到这道题不会做,咋办? 先从简单的情况来考虑.
加入给出的 c 序列中每个 c 都相等,那么显然可以用一个dp去做.
既然每个数都为 c , 那么 a 序列中的每个值肯定也都是 \geq c 的.
设 >c 的数的个数为 x, 那么有 x=10^9-c.
原问题就转化为了在数列上填数,每连续的 k 格中必须有一个是 c 的方案数.
定义状态 f_i 为序列长度为 i ,第 i 个数必须刚好等于 c 的合法方案数,那么我们有:
f_i=\sum_{j=1}^{j\leq k}x^{j-1}*f_{i-j}
$x^{j-1}$ 即中间空出来的 $j$ 个格子不能刚好填 $c$ 的总填法数.
这样是 $O(nk)$, 经过观察,可以发现这个计算式子长得很像一个等比数列. 那可以进行一些骚操作:
$$x*f_i=\sum_{j=1}^{j\leq k}x^j*f_{i-j}$$
$$f_{i+1}=\sum_{j=1}^{j\leq k}x^j*f_{i-j+1}$$
容易发现,这两个和式中有很多重复的东西,把他们相减抵消掉,就可以得到:
$$f_{i+1}-x*f_i=f_i-x^k*f_{i-k}$$
$$f_{i+1}=(x+1)*f_i-x^k*f_{i-k}$$
好的,现在我们有一个 $O(n)$ 的计算方法了.考虑如何推广到原问题.
对于 $c$ 序列中一段连续一样的数字,我们可以把他们合并在一起.
考虑这样的一个连续段 $c_i=c_i+1=\dots=c_{len}$, 假设 $c_{i-1}>c_i$, 那么就可以有:
$$\min(a_{i-1},a_i,a_{i+1},\dots,a_{i+k-2})=c_{i-1}$$
$$\min(a_i,a_{i+1},a_{i+2},\dots,a_{i+k-1})=c_i$$
可以发现,在多了 $a_{i+k-1}$ 这个数之后,最小值从 $c_{i-1}$ 变为了 $c_i$, 而 $c_{i-1}>c_i$, 所以可以得到 $a_{i+k-1}=c$. 而 $[i,i+k-2]$ 这个区间里的数因为有了 $a_{i+k-1}=c$, 所以并不用去考虑 $c_i$ 这个限制,只需要考虑之前的 $c_{i-1}$ 的限制就好了.
这样,我们相当于把这个长度为 $len$. 的序列的前 $k$ 个数给挖掉了.(前 $k-1$ 个会在之前考虑, 第 $k$ 个已经确定)
那么对于 $c_{len}<c_{len+1}$ 的情况也是这样的,相当于从末尾挖掉 $k$ 个数字.
挖掉这些数字之后,每一段相对就是独立的了. 那么用上面的dp算出答案,简单相乘即可.
----------
贴上代码(参考了xzz大佬的写法)
```
#include<cstdio>
#include<cstdlib>
#define mod 1000000007
#define maxn 200005
#define LIM 1000000000
using namespace std;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return 1ll*x*y%mod;}
int ksm(int a,int b)
{
int s=1;
for(;b;a=mul(a,a),b>>=1)
if(b&1) s=mul(s,a);
return s;
}
int f[maxn],a[maxn],n,k;
int Solve(int len,int v)
{
f[0]=1,f[1]=1; int pw=ksm(LIM-v,k);
for(int i=2;i<=len+1;i++)
{
f[i]=mul(LIM-v+1,f[i-1]);
if(i-k-1>=0) f[i]=sub(f[i],mul(pw,f[i-k-1]));
}
return f[len+1];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n-k+1;i++) scanf("%d",&a[i]);
int ans=1;
for(int i=1,j=1;i<=n-k+1;i=j+1)
{
for(j=i;a[i]==a[j]&&j<=n-k+1;j++);
j--; int len=j-i+k;
if(i>1&&a[i-1]>a[i]) len-=k;
if(j<n-k+1&&a[j+1]>a[j]) len-=k;
if(len>0) ans=mul(ans,Solve(len,a[i]));
}
printf("%d\n",ans);
}
```