[arc059] F - Unhappy Hacking

Problem

你有一个空串，可以进行 \(n\) 次操作。
操作分三种：

1. 在字符串末尾添加字符 0。
2. 在字符串末尾添加字符 1。
3. 删除末尾字符。

问你有多少种操作方案，使得最终得到的字符串为目标串，答案对 \(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;
}