SRM319 div1 medium
ACRushさすが。
#include <set> #include <vector> typedef long long LL; using namespace std; class ConstructBST { public: int n; LL ans; LL C[30][30]; set<int> se; int rec(int pos) { if(se.find(pos)==se.end()) return 0; else { int left=rec(pos*2); int right=rec(pos*2+1); ans*=C[left][right]; return left+1+right; } } LL numInputs(vector <int> tree) { se.clear(); n=tree.size(); ans=1; for(int i=0;i<n;i++) se.insert(tree[i]); for(int i=0;i<30;i++) for(int j=0;j<30;j++) C[i][j]=(i==0 || j==0)?1:C[i-1][j]+C[i][j-1]; rec(1); return ans; } };