C++14(g++5.4) 解法, 执行用时: 137ms, 内存消耗: 456K, 提交时间: 2019-05-16 11:36:10

#include <bits/stdc++.h>
using namespace std;

int main() {
	const uint64_t mod = 1000000007;
	auto add = [&mod] (const uint64_t& a, const uint64_t& b) { return a + b < mod ? a + b : a + b - mod; };
	auto mul = [&mod] (const uint64_t& a, const uint64_t& b) { return a * b % mod; };
	const size_t maxn = 5000;
	vector<uint64_t> dp0(maxn + 1), dp1(maxn + 1);
	dp0[1] = dp1[1] = 1;
	for (size_t i = 2; i <= maxn; ++i) for (size_t j = 1; j != i; ++j) {
		dp0[i] = add(dp0[i], mul(dp0[j], add(dp0[i - j], dp1[i - j])));
		dp1[i] = add(dp1[i], add(mul(dp0[j], dp1[i - j]), mul(dp1[j], add(dp0[i - j], dp1[i - j]))));
	}
	size_t T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		cout << dp0[n] << endl;
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 148ms, 内存消耗: 488K, 提交时间: 2019-05-13 09:01:45

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
const int Mod=1000000007;
int f[MAXN][2];
int main()
{
    f[1][0]=f[1][1]=1;
    for(int i=1;i+1<MAXN;i++)
        for(int j=0;j<i;j++)
        {
            f[i+1][0]=(f[i+1][0]+1LL*f[j+1][0]*(f[i-j][0]+f[i-j][1]))%Mod;
            f[i+1][1]=(f[i+1][1]+1LL*f[j+1][0]*f[i-j][1])%Mod;
            f[i+1][1]=(f[i+1][1]+1LL*f[j+1][1]*(f[i-j][0]+f[i-j][1]))%Mod;
        }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",f[n][0]);
    }
    return 0;
}