天天看點

[usaco]Cow Pedigrees

題意:給你一棵數的節點個數以及它的高度,已知這棵樹的每個節點,要麼有兩個孩子,要麼沒有孩子,問你有多少種不同的構造方法(mod 9901)

解題思路:這個題首先要考慮到的就是組合數的取摸,(http://hi.baidu.com/aekdycoin/item/e051d6616ce60294c5d249d7),然後我最開始想到的方法是dfs。。發現逾時,原因是一層中的節點,我們隻需要考慮其個數,不需要考慮其位置,最後想到了3維DP,三個參數分别為層數,這層節點的個數,以及還剩下節點的個數,

解題代碼:

[usaco]Cow Pedigrees
[usaco]Cow Pedigrees

View Code

另一種方法:一棵樹的狀态是取決于它左右子節點!