40pts玄关求条(新思路)

#include<iostream>
using std::cin;
using std::cout;
int c[4300][4300];
long long n, p, f[4300][4]; //f[0] 左右山谷 [1] 左右山峰 [2]左山峰 [3]右山峰
signed main()
{
	cin >> n >> p;
	c[0][0] = 1;
	for (int i = 1; i < 4300; i++)
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
		{
			c[i][j] = ((long long)c[i - 1][j] + c[i - 1][j - 1]) % p;
			c[i][j] %= p;
		}
	}
	f[1][0] = 1;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < i; j++) //左半边有多少个
		{
			long long times = c[i - 1][j];
			for (int pp = 0; pp < 4; pp++)
			{
				switch (pp)
				{
					case 0:
						if (i % 2 == 0)
							break;
						if (j == 0 || j == i - 1)
							break;
						f[i][pp] += times * f[j][0] * f[i - 1 - j][0];
						f[i][pp] %= p;
						break;
					case 1:
						if (i % 2 == 0)
							break;
						if (j == 0 || j == i - 1)
							f[i][pp] += times * (f[j][2] + f[i - 1 - j][3]);
						else
							f[i][pp] += times * f[j][2] * f[i - 1 - j][3];
						f[i][pp] %= p;
						break;
					case 2:
						if (i % 2)
							break;
						if (j == 0)
							f[i][pp] += times * f[i - 1 - j][0];
						else if (j == i - 1)
							break;
						else
							f[i][pp] += times * f[j][2] * f[i - 1 - j][0];
						f[i][pp] %= p;
						break;
					case 3:
						if (i % 2)
							break;
						if (j == 0)
							break;
						else if (j == i - 1)
							f[i][pp] += times * f[i - 1][0];
						else
							f[i][pp] += times * f[j][0] * f[i - 1 - j][3];
						f[i][pp] %= p;
						break;
				}
			}
		}
	}
	cout << (f[n][0] + f[n][1] + f[n][2] + f[n][3]) % p;
	return 0;
}