有长度为$n$一段数列，每个数字都是非负数，数列的首项和末项均为$0$，相邻两个元素差值$\in {-1,1 }$。给出数列中连续的一段相邻元素的差值，求可能有多少种不同的数列。答案对$1e9+9$取模
$n \leq 50$
形象化地，我们在下文把项的大小称为高度。开始和最后高度都应为0，每时每刻高度都应该是非负数。
一开始感觉和Codeforces629C一模一样。
这是那题的做法:
预处理这样的dp数组
$f[i][j]$表示长度为$i$,数列中最大项为$j$,降到$0$的可能性
$g[i][j]$表示长度为$i$,从$0$升到$j$的可能性
$f$和$g$转移都是一样的，可以视为一个数组
算答案的时候枚举前面的长度以及高度，即可得到后面的长度和高度
但是这两题还是有很大区别的。
CF那题是前面和后面不一样就算两种不同的方案，而在这题里考虑的是所有元素的不同。
用KMP+dp来解决。
令字符串长度为$m$
$f[i][j][k][b]$表示第$i$个数字，在字符串上匹配了$j$, 现在的高度是$k$, $b$=[已经出现目标串]
顺推写的话，对于当前的$f[i][j][k][b]$，如果与字符串上下一个动作相吻合，则高度$k$相应变化，匹配长度$j$相应增加。否则$j$沿着失配函数一直走到匹配位置或者走到$0$。如果某个时刻匹配的长度$j=m$，则更新$b\mid 1$的答案。
当然用AC自动机也是可以的，好像还方便蛮多
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
typedef double db;
typedef unsigned ud;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define ph push
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
const int INF=(ud)-1>>1;
const ll inf=(ull)-1>>1;
template<class T>void rd(T &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
template<class T>void nt(T x){
if(!x)return;
nt(x/10);
putchar(48+x%10);
}
template<class T>void pt(T x){
if(!x)putchar('0');
else nt(x);
}
template<class T>void Max(T &a,T b){
if(a<b)a=b;
}
template<class T>void Min(T &a,T b){
if(a>b)a=b;
}
const int M=55;
const int P=1e9+9;
inline void Mod_add(int &a,int b){
if((a+=b)>=P)a-=P;
}
int f[2][M][M][2],fail[M];
inline void getFail(string &P){
fail[0]=fail[1]=0;
int m=P.length();
for(int i=1;i<m;++i){
int j=fail[i];
for(;j&&P[i]!=P[j];j=fail[j]);
fail[i+1]=P[i]==P[j]?j+1:0;
}
}
class FoxAndMountain {
public:
int count(int n, string s) {
if(n&1)return 0;
memset(f,0,sizeof(f));
memset(fail,0,sizeof(fail));
getFail(s);
int m=s.length();
int cur=0,nxt=1;
f[nxt][0][0][0]=1;//
for(int i=0;i<n;++i){//the i^th time
swap(cur,nxt);
memset(f[nxt],0,sizeof(f[nxt]));
for(int j=0;j<=m;++j){//match the j^th number
for(int k=0;k<n;++k)//the height is k
for(int l=0;l<2;++l){
if(!f[cur][j][k][l])continue;
if(j==m){
int w=fail[j];
for(;w&&'U'!=s[w];w=fail[w]);
Mod_add(f[nxt][w+(s[w]=='U')][k+1][l],f[cur][j][k][l]);
w=fail[j];
for(;w&&'D'!=s[w];w=fail[w]);
if(k)Mod_add(f[nxt][w+(s[w]=='D')][k-1][l],f[cur][j][k][l]);
continue;
}
if(s[j]=='U'){
Mod_add(f[nxt][j+1][k+1][l|((j+1)==m)],f[cur][j][k][l]);
int w=fail[j];
for(;w&&'D'!=s[w];w=fail[w]);
if(k>0)Mod_add(f[nxt][w+(s[w]=='D')][k-1][l],f[cur][j][k][l]);
}
else{
if(k>0)Mod_add(f[nxt][j+1][k-1][l|((j+1)==m)],f[cur][j][k][l]);
int w=fail[j];
for(;w&&'U'!=s[w];w=fail[w]);
Mod_add(f[nxt][w+(s[w]=='U')][k+1][l],f[cur][j][k][l]);
}
}
}
}
int res=0;
for(int j=0;j<=m;++j)
Mod_add(res,f[nxt][j][0][1]);
return res;
}
};