Tree Maker
Problem DescriptionTree Lover loves trees crazily.One day he invents an interesting game which is named Tree Maker.
In this game, all trees are binary trees.
Initially, there is a tree with only one vertex and a cursor on it. Tree Lover can control the cursor to apply 5 operations to build a tree, and their formats are following:
0 : Jump to the parent of the current vertex.
1 : Jump to the left child of the current vertex.
2 : Jump to the right child of the current vertex.
3 x : Generate a tree with x vertices arbitrarily and make it the left subtree of the current vertex.
4 x : Generate a tree with x vertices arbitrarily and make it the right subtree of the current vertex.
When applying an operation, the log system will log down a record of it.
Tree Lover played this game for a whole day yesterday. As a forgetful man, although Tree Lover knew the shape of the tree while playing, after a sleep he forgot it.
All he has now is the logs of operations.
Tree Lover wants to know: how many possible shapes of the tree can have yesterday according to the logs?
Can you answer this question?
InputThe input consists of multiple test cases.For each test case:
The first line is an integer n (1 <= n <= 500), denoting the lines of logs.
Then follow n lines of logs. The formats of logs are as described above.
The integer x of operation 3 and 4 is positive.
In each case, the number of vertices of the tree will never exceed 500.
You can assume that the cursor will never jump to a non-existent vertex.
If the left child of a vertex exists, operation 3 will not be applied on this vertex, and operation 4 is similar.
OutputFor each test case, ouput a single line “Case #x: y”, where x is the case number, starting from 1, and y is the answer to Tree Lover’s question.Because the answer can be large, please output the answer mod 1000000007.
Sample Input23 34 323 31Sample OutputCase #1: 25Case #2: 5HintBecause the tree is a binary tree, if left and right subtrees of a vertex are of different shapes, after swapping them, the new tree is considered different from the original one.
有一个造二叉树的程序,初始时只有一个节点并且光标指向它,然后进行了n次操作,每次操作属于以下5种操作之一:
- 光标指向当前节点的父亲节点.
- 光标指向当前节点的左儿子.
- 光标指向当前节点的右儿子.
- 随机造一棵包含x个节点的二叉树,把它作为当前节点的左子树.
- 随机造一棵包含x个节点的二叉树,把它作为当前节点的右子树.
给出这n个操作,求在满足所有操作合法的前提下,共有多少种可能的二叉树被造出来,对109+7取模.
1≤n≤500,∑x<500.
【分析】
这是我做的最难的卡特兰数了，然而难在打的方面，真的要想清楚才行啊！！主要是dp部分，卡特兰数是求二叉树形态的。
当只有操作1~3，我们可以准确知道这棵树，就是说我们可以准确知道这棵树的一部分，
然后对于操作4~5，我们知道要插入i棵小树，一共j的点这样的信息。
当要插入一颗大小为k的树时，方案数=卡特兰（k），
然后dp求出用j个节点构成i棵可以为空的子树的方案数f[i][j],然后在树上走一遍然后统计即可。
重点是求当前对于询问能插子树的位置以及未知点的个数。
上图，箭头边x->y表示在x那里有一个插子树操作。（箭头指向位置可以为空，因为那个位置是未知的，插了一颗子树但是没有走到）。
无向边表示没有进行插树操作但是走到了这个点，就是说这是给我们知道的对于未知子树的特别信息，是我们可以确定部分子树形态。
操作每个点记录一个is[x]，sum[x]，sum[x]表示从x开始，不走箭头边能一共走到的点的个数。
is[x]表示从x开始不走箭头边走到的点的插位个数（就是如果没有左孩子，就有1个插位位置，右孩子也一样）
为什么要这样呢？如上图，1，2都有一个插左子树操作，那么3节点必定不是执行1插子树操作时产生的，2左子树上其他点也是如此，所以不能计入1操作的答案里。
所以如果统计1插左子树操作时，询问一下2的sum[x]和is[x]即可，最后加上dp就好了。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define LL long long
#define Mod 1000000007
#define Maxn 510 LL p[*Maxn],c[Maxn];
LL f[Maxn][Maxn]; LL qpow(LL x,LL b)
{
LL ans=;
while(b)
{
if(b&) ans=(ans*x)%Mod;
x=(x*x)%Mod;
b>>=;
}
return ans;
} LL get_c(LL n)
{
LL k=qpow(p[n+],Mod-),ans=;
ans=(p[*n]*k)%Mod;
k=qpow(p[n],Mod-);
ans=(ans*k)%Mod;
return ans;
} void init()
{
p[]=;
for(LL i=;i<=*Maxn-;i++) p[i]=(p[i-]*i)%Mod;
for(LL i=;i<=Maxn-;i++) c[i]=get_c(i);
memset(f,,sizeof(f));
f[][]=;
for(LL i=;i<=Maxn-;i++) f[][i]=c[i]; for(LL i=;i<=Maxn-;i++)
for(LL j=;j<=Maxn-;j++)
{
// f[i][j]=0;
for(LL k=;k<=j;k++)
f[i][j]=(f[i][j]+f[i-][j-k]*c[k])%Mod;
} } struct node
{
int x,lc,rc,f;
int sum,is;
bool al,ar;
}t[Maxn];int cnt; struct hp
{
int x,id;
bool q;
}qy[Maxn];int ql; void upd(int x)
{
t[x].is=; t[x].sum=;
t[x].sum+=t[x].al?:t[t[x].lc].sum;
t[x].sum+=t[x].ar?:t[t[x].rc].sum; int y;
y=t[x].lc?t[t[x].lc].is:;
if(t[x].al) y=;
t[x].is+=y; y=t[x].rc?t[t[x].rc].is:;
if(t[x].ar) y=;
t[x].is+=y;
} int n;
bool ffind()
{
int now=;cnt=;ql=;
t[].lc=t[].rc=;
t[].al=t[].ar=;
upd();
bool ok=;
for(int i=;i<=n;i++)
{
int opt;
scanf("%d",&opt);opt++;
if(opt==)
{
if(now==) ok=;
now=t[now].f;
}
else if(opt==)
{
if(!t[now].lc)
{
t[++cnt].f=now;
t[cnt].lc=t[cnt].rc=;
t[cnt].al=t[cnt].ar=;
upd(cnt);
t[now].lc=cnt;
upd(t[cnt].f);
}
now=t[now].lc;
}
else if(opt==)
{
if(!t[now].rc)
{
t[++cnt].f=now;
t[cnt].lc=t[cnt].rc=;
t[cnt].al=t[cnt].ar=;
t[now].rc=cnt;
}
now=t[now].rc;
}
else if(opt==)
{
if(t[now].al||t[now].lc) ok=;
int x;
scanf("%d",&x);
qy[++ql].id=now;qy[ql].x=x;qy[ql].q=;
t[now].al=;
}
else
{
if(t[now].ar||t[now].rc) ok=;
int x;
scanf("%d",&x);
qy[++ql].id=now;qy[ql].x=x;qy[ql].q=;
t[now].ar=;
}
}
return ok;
} void dfs(int x)
{
if(t[x].lc) dfs(t[x].lc);
if(t[x].rc) dfs(t[x].rc);
upd(x);
} LL get_ans()
{
LL ans=;
for(int i=;i<=ql;i++)
{
int now,y=qy[i].x;
if(qy[i].q==)
{
if(t[qy[i].id].lc) now=t[t[qy[i].id].lc].is,y-=t[t[qy[i].id].lc].sum;
else now=;
}
else
{
if(t[qy[i].id].rc) now=t[t[qy[i].id].rc].is,y-=t[t[qy[i].id].rc].sum;
else now=;
}
if(y<) return ;
ans=(ans*f[now][y])%Mod;
}
return ans;
} int main()
{
int T,kase=;
init();
while(scanf("%d",&n)!=EOF)
{
printf("Case #%d: ",++kase);
if(!ffind()) {printf("0\n");continue;}
dfs();
printf("%lld\n",get_ans());
}
return ;
}
[HDU 5370]
2016-09-21 22:12:01