题解：AT_s8pc_4_e Enormous Atcoder Railroad
Meta_Morph
·
·
题解
AT_s8pc_4_e Enormous Atcoder Railroad 题解
博客园链接：AT_s8pc_4_e Enormous Atcoder Railroad 题解 - Add_Catalyst - 博客园 (cnblogs.com)。
知识点
DP。
分析
$$
f_{i,j,j} = \sum_{len=1}^{2(X-j)} f_{i-len,j,j+1} + [i\le 2(X-j)+1] \\
f_{i,j,j+1} = \sum_{len=1}^{2(X-j)} f_{i-len,j+1,j+1} + [i\le 2(X-j)] \\
$$
我们简化一下状态，设 $f'_{i,j,0/1} = f_{i,j,j/j+1}$，转移变为下式：
$$
f'_{i,j,0} = \sum_{len=1}^{2(X-j)} f'_{i-len,j,1} + [i\le 2(X-j)+1] \\
f'_{i,j,1} = \sum_{len=1}^{2(X-j)} f'_{i-len,j+1,0} + [i\le 2(X-j)] \\
$$
前缀和优化即可 $O(X\max{\Delta S})$ 解决。最后统计答案为：
$$
\prod_{i=0}^{m-2} f'_{s_{i+1}-s_{i},i,1}
$$
### 优化
发现空间太大，时间常数也太大，考虑把后两维 $j,0/1$ 一起滚动数组压掉，空间剩下 $O(n)$，时间常数极小。
## 代码
```cpp
constexpr int N(1e4+10),M(2.5e3+10);
int n,m,X,ans,lim;
int a[M],f[N];
signed main() {
/*DE("Input");*/
I(n,m,X);
if(m-1>X)return puts("0"),0;
FOR(i,0,m-1)I(a[i]);
FOR(i,0,m-2)tomax(lim,a[i+1]-a[i]);
/*DE("DP");*/
ans=1;
DOR(j,X,0) {
if(j<X) {
DOR(i,lim,1) {
f[i]=add(f[i-1],i<=2*(X-j));
if(2*(X-j)<i)toadd(f[i],Mod-f[i-2*(X-j)-1]);
}
if(j<=m-2)tomul(ans,f[a[j+1]-a[j]]);
FOR(i,1,lim)toadd(f[i],f[i-1]);
}
if(j>0) {
DOR(i,lim,1) {
f[i]=add(f[i-1],i<=2*(X-j)+1);
if(2*(X-j)<i)toadd(f[i],Mod-f[i-2*(X-j)-1]);
}
FOR(i,1,lim)toadd(f[i],f[i-1]);
}
}
/*DE("Output");*/
O(ans,'\n');
return 0;
}
```
------