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 釋出。