<div class="post_brief"><p>
什么鬼。</p>

 

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

 

然后直接暴力是O(n3)的。在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", &amp;t);
while (t --) {
    scanf("%d%d", &amp;n, &amp;k);
    if (!k)
        puts((n == 1) ? "1" : "0");
    else {
        s = getf(k, n) - getf(k - 1, n);
        if (s &lt; 0)
            s += mod;
        printf("%d\n", s);
    }
}



}