什么鬼。

很好想的dp。f[i][j]表示深度不超过i且大小为j的二叉树的个数。转移是f[i][j] = ∑(f[i - 1][k] * f[i - 1][j - k - 1])。

然后直接暴力是O(n³)的。在spoj上能过在bzoj上不能过。在bzoj上得用记忆化搜索来减掉一些无用的东西。虽然我觉得很烦。

然后试图用fft，发现fft比暴力还慢。然后试图用fnt，然后发现fnt好像不能对1e9+7这种质数用。因为1e9+6只有来一个2。真悲伤。我还是太弱啊。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
const int maxn = 609;
const int mod = 1000000007;
 
#define _l (long long int)
 
int f[maxn][maxn];
 
int getf(int i, int j) {
    if (i == 0)
        return j <= 1;
    else if (j == 0)
        return 1;
    else if (f[i][j] == -1) {
        f[i][j] = 0;
        for (int k = 0; k < j; ++ k)
            f[i][j] = (f[i][j] + _l getf(i - 1, k) * getf(i - 1, j - k - 1)) % mod;
    }
    return f[i][j];
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
 
    memset(f, -1, sizeof(f));
    int t, n, k, s;
    scanf("%d", &t);
    while (t --) {
        scanf("%d%d", &n, &k);
        if (!k)
            puts((n == 1) ? "1" : "0");
        else {
            s = getf(k, n) - getf(k - 1, n);
            if (s < 0)
                s += mod;
            printf("%d\n", s);
        }
    }
}