Count & 树的同构 解题报告
之所以两道题放在一起，就是因为他们很相似。
题目一：Count
大项堆是具有如下性质的二叉树：
- 它的任意一个父亲节点的权值总是比孩子的权值要大
- 它是一颗完全二叉树
先给定这个堆的节点个数N，假如每个节点的权值都为在1—N之间的整数且各不相同，求可能的大项堆的个数。当然，这个个数可能很多，这里只要求这个个数模K即可。
输入： 两个用空格隔开的整数N和Q（N<30,Q<10^9） 输出： 可能的大项堆的个数模Q
输入样例： 3 1000 输出样例： 2
题目二：树的同构
排序二叉树是我们熟悉的一种数据结构，这里提到的排序二叉树都是指根的关键字比左子树上的所有点都大，比右子树上的都小（假定不存在相同的关键字）的排序二叉树。如果给定一个输入序列，按照这个序列依次将各个结点插入，我们就得到了一棵排序二叉树。例如，输入序列 4 2 1 3 5 对应如下排序二叉树：2 4 5 1 3。而输入序列 4 5 2 1 3 以及 4 2 5 1 3 都对应同样的树，我们说这三个序列同构。
现在给定一个长度为 N 的输入序列，求与之同构的序列有多少个（包括这个序列本身）。由于问题的答案可能比较大，只要求输出答案 mod 10,007 的结果。
Input 第 1 行：一个正整数 N，即输入序列长度。 第 2 行：N 个 1 到 N 之间的正整数，数字相互之间不重复。
Output 仅有一行，即同构序列数 mod 10,007 的长度。
Sample Input
5
4 2 1 3 5
Sample Output
8
样例解释： 即 4 2 1 3 5、4 2 1 5 3、4 2 3 1 5、4 2 3 5 1、4 5 2 1 3、4 5 2 3 1、4 5 3 1 2、4 5 3 2 1 这八组输入顺序。
数据范围： 对于 100% 的数据，N <= 1,000，每组数据 10 分。 对于 120% 的数据，N <= 100,000，每组数据 20 分。
思路分析
这两个题目主要在于初始化的不同。Count 可以自己虚拟建树，而 树的同构 则必须按要求建树。建过树之后，这两个题目是完全相同的，都是树形动态规划。用DP[r]表示节点r为根的树所能产生的种类或其mod后的数值。 动态转移方程为：
dp[r] = dp[r.左树] * dp[r.右树] * 求组合数(左右子树的节点数之和, 左/右子树的节点数（用数学可轻易证明左/右子树的节点数的结果相同）)
其实质是，对于一个父亲，如何安排它的孩子的情况呢？那就要挑选出一部分数字（对于题目count）（对于树的同构是位置）安排给左子树使用，其余的数字（或位置）自然就分给右子树了。用组合而不是排列，原因是对于每一个组合，具体如何排列这些数字或位置，已经由子树DP的数值所包括。题目容易被误解为使用排列。
完整代码
//By Ceeji
//Date: 2009-4-9
//HAOI test 6 - Problem 1 : count
//Type : Tree DP
//State: Accepted
Program count;
Const
fin='count.in';
fou='count.out';
Var
n,q,c,ci,i:longint;
comb:array[0..31,0..31]of longint;
dp:array[0..100,1..2]of int64;
tree:array[0..100]of boolean;
Function GetComb(m,n:longint):longint;
begin
if m=n then exit(1);
if n=0 then exit(1);
if n=1 then exit(m);
if comb[m,n]<>0 then exit(comb[m,n]);
comb[m,n]:=((getComb(m-1,n) mod q)+(getComb(m-1,n-1) mod q)) mod q;
exit(comb[m,n]);
end;
Procedure dpit(p:longint);
begin
if not tree[p] then begin dp[p,1]:=1 mod q; dp[p,2]:=0; exit; end;
dpit(p<<1);
dpit(p<<1+1);
dp[p,2]:=dp[p<<1,2]+dp[p<<1+1,2]+1;
dp[p,1]:=getComb(dp[p,2]-1,dp[p<<1,2]);
dp[p,1]:=(dp[p,1]*dp[p<<1,1])mod q;
dp[p,1]:=(dp[p,1]*dp[p<<1+1,1])mod q;
end;
begin
assign(input,fin); reset(input);
assign(output,fou); rewrite(output);
readln(n,q);
close(input);
fillchar(comb,sizeof(comb),0);
fillchar(tree,sizeof(tree),0);
c:=1; ci:=1;
for i:=1 to n do
begin
if c=1 then
begin
tree[ci]:=true;
ci:=1; inc(c);
end
else begin
tree[2<<(c-2)+ci-1]:=true;
if ci=2<<(c-2) then begin ci:=1; inc(c); end else inc(ci);
end;
end;
fillchar(dp,sizeof(dp),0);
dpit(1);
writeln(dp[1,1] mod q);
close(output);
end.
完整代码：树的同构
//By Ceeji
//HAOI test 5 - Problem 2 : Tree
//Date: 2009-3-31
//Type : Tree DP
//State: Accepted
Program tree;
Const
inf='tree.in';
ouf='tree.out';
Type
node=record
v,l,r:longint;
end;
Var
n,i,j,m:longint;
t:array[1..1000]of node;
comb:array[0..1000,0..1000]of longint;
dp:array[0..1000,1..2]of longint;
Procedure add(j,i:longint);
begin
if j<t[i].v then
begin
if t[i].l=0 then begin inc(m); t[i].l:=m; t[m].v:=j; end
else begin add(j,t[i].l); end;
end
else
begin
if t[i].r=0 then begin inc(m); t[i].r:=m; t[m].v:=j; end
else begin add(j,t[i].r); end;
end;
end;
Function getcomb(n,m:longint):longint;
begin
if comb[n,m]<>0 then exit(comb[n,m]);
if m=1 then exit(n);
if (n=m)or(m=0) then exit(1);
comb[n,m]:=(getcomb(n-1,m)+getcomb(n-1,m-1))mod 10007;
exit(comb[n,m]);
end;
Procedure dpit(p:longint);
begin
if dp[t[p].l,1]=0 then dpit(t[p].l);
if dp[t[p].r,1]=0 then dpit(t[p].r);
dp[p,1]:=(((dp[t[p].l,1]*dp[t[p].r,1])mod 10007)*getcomb(dp[t[p].l,2]+dp[t[p].r,2],dp[t[p].l,2]))mod 10007;
dp[p,2]:=1+dp[t[p].l,2]+dp[t[p].r,2];
end;`
begin
assign(input,inf); reset(input);
assign(output,ouf); rewrite(output);
readln(n);
fillchar(t,sizeof(t),0); m:=1;
read(j); t[1].v:=j;
for i:=2 to n do
begin
read(j);
add(j,1);
end;
close(input);
fillchar(dp,sizeof(dp),0);
fillchar(comb,sizeof(comb),0);
dp[0,1]:=1;
dp[0,2]:=0;
dpit(1);
writeln(dp[1,1]);
close(output);
end.
本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。