bzoj3769 spoj 8549 BST again

题解：

比较水的题目

普通dp其实复杂度还是比较大的

可以任意模数ntt优化。。

但好像没人写。。

代码：

#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
const int mo=1e9+7;
int n,m,f[1000][1000];
int main()
{
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
  ios::sync_with_stdio(false);
  int T;
  cin>>T;
  while (cin>>n>>m)
  {
    m++;
  /*  f[0][0]=1;
    rep(i,1,n)
      f[1][i]=f[0][i]=1;
    rep(i,2,n)
    {
      rint tmp=min(i,m);
      rep(j,1,tmp)
      {
        rint tmp=0,m1,m2;
        rep(k,0,i-1)
        {
          m1=f[k][j-1]; m2=f[i-k-1][j-1];
          if (m1&&m2) tmp=(tmp+1ll*m1*m2)%mo;
        }
        f[i][j]=tmp;
      }
      rep(j,min(i,m)+1,max(n,m))
        f[i][j]=f[i][j-1];
    } */
    f[0][0]=1;
    rep(i,1,n) f[i][1]=f[i][0]=1;
    rep(i,2,m)
      rep(j,2,n)
      {
        rint tmp=0;
        rep(k,0,j-1)
        {
          tmp=(tmp+1ll*f[i-1][k]*f[i-1][j-k-1])%mo;
        }
        f[i][j]=tmp;
      }
     cout<<(f[m][n]-f[m-1][n]+mo)%mo<<endl;        
    //cout<<(f[n][m]-f[n][m-1]+mo)%mo<<endl;
  }
  return 0; 
}