文本解題報(bào)告

1、Another Counting Problem解題摘要題意簡(jiǎn)述定義嚴(yán)格 n 叉樹(shù)為：所有非葉子節(jié)點(diǎn)都恰好有 n 個(gè)孩子節(jié)點(diǎn)的樹(shù)。計(jì)算深度恰好為 d+1的嚴(yán)格 n 叉樹(shù)的個(gè)數(shù)。其中，一個(gè)節(jié)點(diǎn)的各個(gè)孩子是有序的。（詳見(jiàn)原題）初步分析本題是一個(gè)計(jì)數(shù)問(wèn)題。由于樹(shù)結(jié)構(gòu)清晰的分為 d+1 層，很容易想到以層為階段進(jìn)行遞推。很明顯，除了根節(jié)點(diǎn)以外，樹(shù)上每一層的節(jié)點(diǎn)數(shù)都是 n 的倍數(shù)。而這個(gè)倍數(shù)恰好就表示本層是由上一層的幾個(gè)點(diǎn)擴(kuò)展而來(lái)的。由于樹(shù)上一個(gè)節(jié)點(diǎn)的各個(gè)孩子是需要考慮順序的，那么如果兩棵樹(shù)第 k 層上的的節(jié)點(diǎn)總數(shù)相同，那么不論樹(shù)的上半部什么形狀，下面的的部分的變化總數(shù)是相同的。因此，可以從樹(shù)的根部向下

2、進(jìn)行遞推。f(k,t)表示，深度為 k+1，且在第 k+1 層上有nt 個(gè)節(jié)點(diǎn)的嚴(yán)格 n 叉樹(shù)的總數(shù)。這樣，可以每次在當(dāng)前的樹(shù)下面加上一層，也就是在當(dāng)前最底層節(jié)點(diǎn)中選一些分叉的點(diǎn)，進(jìn)而推到下一層。具體一些說(shuō)，在計(jì)算 f(k,t)時(shí)，需要枚舉上一層的底層節(jié)點(diǎn)個(gè)數(shù)。如果上一層的底層節(jié)點(diǎn)有 ni 個(gè)，那么這種情況下本層有 nt 個(gè)節(jié)點(diǎn)的樹(shù)的個(gè)數(shù)就是 f(k1,i)乘以從 ni 個(gè)節(jié)點(diǎn)中選出 t 個(gè)節(jié)點(diǎn)分叉的方案數(shù)。遞推公式如下：1此處分析的時(shí)間空間復(fù)雜度都不包精度的復(fù)雜度。算法一算法二基本思路遞推遞推時(shí)間復(fù)雜度1O(d(nd)2)O(dlog2n)空間復(fù)雜度O(nd)O(1)其中初始條件是 f(1,

3、1)=1，而對(duì)于深度為 1 的情況則需要特殊處理，直接輸出1。否則就統(tǒng)計(jì) f(d,i)的總和（其中，1ind1），這就是最后的。時(shí)空分析一上面的遞推方法，狀態(tài)總數(shù)為 d nd。由于遞推是一層一層進(jìn)行的，因此可以使用滾動(dòng)數(shù)組，這樣，空間復(fù)雜度為 nd。時(shí)間方面，狀態(tài)轉(zhuǎn)移中，需要枚舉一遍 i，并且需要計(jì)算組合數(shù)，這樣的時(shí)間約為(nd)2?？梢詫?duì)組合數(shù)的計(jì)算進(jìn)行一定的優(yōu)化，完全可以從以前計(jì)算的組合數(shù)通過(guò)一次乘法一次除法得出。這樣，不考慮高精度的時(shí)間，狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度約為 nd。再乘以狀態(tài)總數(shù)，遞推算法的時(shí)間復(fù)雜度約為O(d(nd)2)。當(dāng)然，上面時(shí)間復(fù)雜度的分析是比較粗略的。本題中，由于保證了

4、nd 不超過(guò) 210，也就決定了 n 和 d 的取值范圍有一定的限制。n 較大時(shí)，d 就很小，那么狀態(tài)數(shù)就減少了，時(shí)間復(fù)雜度相應(yīng)的降低。d 較大時(shí)，n 就不會(huì)很大，那么的位數(shù)就不會(huì)很高了，高精度計(jì)算的時(shí)間也會(huì)變少。因此，整個(gè)算法的時(shí)間效率是勉強(qiáng)可以接受的。深入分析但上面的算法畢竟不令人滿意，須要尋找到更好的辦法。在上一個(gè)算法中，我們是每次在當(dāng)前的樹(shù)底部加上一層，推倒新的狀態(tài)。如果換一種思路，每次將 n 棵深度不超過(guò) k 的樹(shù)（其中至少有一棵深度恰好為 k）進(jìn)行遞推。為一棵深度為 k+1 的樹(shù)，根據(jù)這種思路那么如果分別知道深度為 1 至 k 的嚴(yán)格 n 叉樹(shù)的數(shù)量，如何計(jì)算深度為 k+1 的嚴(yán)格

5、 n叉樹(shù)種類(lèi)呢。問(wèn)題的關(guān)鍵在于以根節(jié)點(diǎn)孩子為根的 n 棵子樹(shù)中至少要有一棵深度為 k。如果正面計(jì)算，使用容斥原理，復(fù)雜度很高，計(jì)算也非常復(fù)雜，容易出錯(cuò)。利用“補(bǔ)集轉(zhuǎn)化”，計(jì)算出深度不超過(guò) k+1 的嚴(yán)格 n 叉樹(shù)的總和，再減去深度不超過(guò) k 的 n 叉樹(shù)方案數(shù)。也就求出了深度為 k+1 的嚴(yán)格 n 叉樹(shù)的數(shù)量。問(wèn)題在于如何計(jì)算深度在 2 至 t 之間的嚴(yán)格 n 叉樹(shù)的總數(shù)量。可以這樣理解，選出n 棵深度在 1 至 t1 之間的嚴(yán)格 n 叉樹(shù)，將它們排好順序，然后讓他們成為根節(jié)點(diǎn)的孩子，這樣新的樹(shù)也就增加了一層。定義 Ck 表示深度為 k+1 的嚴(yán)格 n 叉樹(shù)總和，Sk 則表示深度在 1 到 k

6、+1 之間嚴(yán)格 n叉樹(shù)的總數(shù)。遞推計(jì)算深度在 2 至 t 之間的 n 叉樹(shù)數(shù)量時(shí)，根節(jié)點(diǎn)的每一個(gè)孩子都可以選擇St2 種樹(shù)，也就是方案總數(shù)為 (St2)n 種。因此，棵一的到下面的遞推公式：其中，C0=C1=S0=1，S1=2。最后的也就是 Cd。時(shí)空分析二上面的遞推算法，明顯的比第一種算法簡(jiǎn)單許多。各種狀態(tài)只有 2d 個(gè)。而由于每次計(jì)算時(shí)，需要用到的值只有 3 個(gè)。因此，利用滾動(dòng)技術(shù)，空間復(fù)雜度是 O(1)的。時(shí)間上，計(jì)算S 的n 次方可以采用反復(fù)平方法，那么每計(jì)算一次Ck 的值就只需要O(log2n)的時(shí)間，總的時(shí)間復(fù)雜度就是 O(dlog2n)，比上一種算法大大改進(jìn)。到此，本題也就得到了很好的解決。小結(jié)解決本題的過(guò)程中，有兩點(diǎn)很需要注意：（1）從算法