Problem
你有一个空串，可以进行 \(n\) 次操作。
操作分三种：
- 在字符串末尾添加字符
0。 - 在字符串末尾添加字符
1。 - 删除末尾字符。
问你有多少种操作方案，使得最终得到的字符串为目标串，答案对 \(10^9+7\) 取模。
\(1 \le n \le 5000，1 \le \left\vert s \right\vert \le n\)
Input
一个整数 \(n\) 和一个字符串 \(s\)。
Output
一行一个整数，表示方案数。
Sample
Input 1
3
0
Output 1
5
Input 2
300
1100100
Output 2
519054663
Input 3
5000
01000001011101000100001101101111011001000110010101110010000
Output 3
500886057
Solution
考虑dp，定义 \(f_{i,j}\) 表示进行 \(i\) 次操作，表示出目标串前 \(j\) 位的方案数。
如果是第一、二种操作， \(f_{i,j}\) 可以由 \(f_{i-1,j-1}\) 转移，但由于 \(j\) 可以为 \(0\)，因此 \(j-1\) 可能为负，需特判。
如果是第三种操作，\(f_{i,j}\) 可以由 \(f_{i-1,j+1}\) 转移。由于删去的字符对答案不会造成影响，所以可以为 \(0\)，也可为 \(1\)。对答案的贡献时两倍的。
因此，\(f_{i,j}=f_{i-1,j-1}+2*f_{i-1,j+1}\)，边界为 \(f_{0,0}=1\)。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 5005;
const int Mod = 1e9 + 7;
int n, m;
string s;
long long f[kmax][kmax];
int main() {
cin >> n >> s;
m = s.size();
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
f[i][0] = (f[i - 1][0] + f[i - 1][1] * 2 % Mod) % Mod; // 特殊处理0的情况
for (int j = 1; j <= i; j++) {
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j + 1] * 2 % Mod) % Mod;
}
}
cout << f[n][m];
return 0;
}