Description：

有左括号，右括号，退格三个键，问打出一个合法括号序列的方案数，空退格无作用。

$1\le n \le 1000$

Solution：

有一个重要的性质是无论括号序列最终长成什么样打出它的方案数都是相同的，根据这个性质就可以分别求打出长为 $2k$ 的序列的方案数乘上 $2k$ 的合法括号序列数，第二部分是卡特兰数，有 $n^2$ 的递推做法，即设 $f[i][j]$ 表示有 $i$ 个字符，剩余未匹配的 $j$ 个左括号，转移枚举放左括号还是右括号， $f[i][j]=f[i-1][j-1]+f[i-1][j+1]$ 。第一部分也是 $DP$ ，设 $f[i][j]$ 表示 $i$ 次操作打出了 $s[1]\sim s[j]$ ， $f[i][j]+=f[i-1][j-1]$ $(j \ge1)$ 代表打出了 $s[j]$ ， $f[i][0]+=f[i-1][0]$ 代表进行了一次无意义的退格， $f[i][j]+=2 \times f[i-1][j+1]$ 代表进行了一次有意义的退格，而退格删掉的可能是左括号也可能是右括号，所以 $\times 2$ ，但是有一个问题，就是状态定义为 $f[i][j]$ 代表打出了 $s[1]\sim s[j]$ ，也就是说 $f[i][j+1]$ 第 $j+1$ 个字符应该已经是确定的了，不应该有两种可能，但是由于上边说过无论序列是什么打出它的状态数都是相同的，所以这些其实是等价的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,p;

#define MAXN 1010

int f[MAXN][MAXN],g[MAXN][MAXN];

int main()

{

	scanf("%d%d",&n,&p);

	f[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= i;++j)

		{

			f[i][j] = (f[i - 1][max(j - 1,0)] + f[i - 1][j + 1] * 2) % p;

		}

	}

	g[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= n;++j)

		{

			if(j >= 1)g[i][j] += g[i - 1][j - 1];

			g[i][j] += g[i - 1][j + 1];

			g[i][j] %= p;

		}

	}

	int ans = 0;

	for(int k = 0;2 * k <= n;++k)

	{

		ans = (ans + g[2 * k][0] * f[n][2 * k]) % p;

	}

	cout << ans << endl;

	return 0;

}