#17772: 現在的學弟好可怕.........


dave0602 (HNO2)

School : 臺北市私立延平高級中學
ID : 42395
IP address : [223.136.167.176]
Last Login :
2020-04-04 14:00:29
e217. 同分異構物(國二理化) -- π | From: [111.250.40.63] | Post Date : 2019-05-19 21:47

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)

 
#17773: Re:現在的學弟好可怕.........


dave0602 (HNO2)

School : 臺北市私立延平高級中學
ID : 42395
IP address : [223.136.167.176]
Last Login :
2020-04-04 14:00:29
e217. 同分異構物(國二理化) -- π | From: [111.250.40.63] | Post Date : 2019-05-19 21:50

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


喔沒事我發現有LaTex
只是我多加一個反斜所以變成五彩繽紛了(?)
還有ZJ不能改原始文章喔><

 
#17782: Re:現在的學弟好可怕.........


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

School : 臺北市私立延平高級中學
ID : 83268
IP address : [203.72.178.252]
Last Login :
2020-03-27 17:06:10
e217. 同分異構物(國二理化) -- π | From: [114.42.218.217] | Post Date : 2019-05-20 19:44

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


喔沒事我發現有LaTex
只是我多加一個反斜所以變成五彩繽紛了(?)
還有ZJ不能改原始文章喔><



像我就很可怕

你說的是3.14學長(方便稱呼的綽號

對不對XD

 
#17790: Re:現在的學弟好可怕.........


314159265358979323846264338327... (少年π)

School : 臺北市私立延平高級中學
ID : 69058
IP address : [111.71.74.37]
Last Login :
2020-04-07 19:35:53
e217. 同分異構物(國二理化) -- π | From: [203.72.178.252] | Post Date : 2019-05-21 16:19

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


喔沒事我發現有LaTex
只是我多加一個反斜所以變成五彩繽紛了(?)
還有ZJ不能改原始文章喔><



像我就很可怕

你說的是3.14學長(方便稱呼的綽號

對不對XD


回亞硝酸學長:
小弟我其實沒有很強,如果真的很強也不會在 NPSC 和校內賽被電爆了QQ

謝謝學長寫的解題報告,不然我連自己在寫什麼都不知道...

n=100000 ?!? 好可怕~

回 ufve0704 學弟:

你加油!

你比我國一的時候還厲害喔

 

 
#17815: Re:現在的學弟好可怕.........


dave0602 (HNO2)

School : 臺北市私立延平高級中學
ID : 42395
IP address : [223.136.167.176]
Last Login :
2020-04-04 14:00:29
e217. 同分異構物(國二理化) -- π | From: [111.71.27.146] | Post Date : 2019-05-22 22:10

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


喔沒事我發現有LaTex
只是我多加一個反斜所以變成五彩繽紛了(?)
還有ZJ不能改原始文章喔><



像我就很可怕

你說的是3.14學長(方便稱呼的綽號

對不對XD


回亞硝酸學長:
小弟我其實沒有很強,如果真的很強也不會在 NPSC 和校內賽被電爆了QQ

謝謝學長寫的解題報告,不然我連自己在寫什麼都不知道...

n=100000 ?!? 好可怕~

回 ufve0704 學弟:

你加油!

你比我國一的時候還厲害喔

 


回3.14學弟:
沒關係還是很強<(_ _)>
不過你測資怎麼生的有點好奇(?)
然後在這裡繼續聊不太方便
或許可以私訊(?)

回ufve0704:
又一個電神OAO!?
怕爆wwwwwww



 
#17816: Re:現在的學弟好可怕.........


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

School : 臺北市私立延平高級中學
ID : 83268
IP address : [203.72.178.252]
Last Login :
2020-03-27 17:06:10
e217. 同分異構物(國二理化) -- π | From: [114.42.219.23] | Post Date : 2019-05-22 22:15

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


喔沒事我發現有LaTex
只是我多加一個反斜所以變成五彩繽紛了(?)
還有ZJ不能改原始文章喔><



像我就很可怕

你說的是3.14學長(方便稱呼的綽號

對不對XD


回亞硝酸學長:
小弟我其實沒有很強,如果真的很強也不會在 NPSC 和校內賽被電爆了QQ

謝謝學長寫的解題報告,不然我連自己在寫什麼都不知道...

n=100000 ?!? 好可怕~

回 ufve0704 學弟:

你加油!

你比我國一的時候還厲害喔

 


回3.14學弟:
沒關係還是很強<(_ _)>
不過你測資怎麼生的有點好奇(?)
然後在這裡繼續聊不太方便
或許可以私訊(?)

回ufve0704:
又一個電神OAO!?
怕爆wwwwwww




但我完全聽不懂DP.....

QAQ

 
#17822: Re:現在的學弟好可怕.........


kerry970176 (ÃςέƗภ)

School : 臺北市私立延平高級中學
ID : 42345
IP address : [111.250.159.191]
Last Login :
2020-04-04 17:59:50
e217. 同分異構物(國二理化) -- π | From: [118.169.186.73] | Post Date : 2019-05-23 19:31

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


喔沒事我發現有LaTex
只是我多加一個反斜所以變成五彩繽紛了(?)
還有ZJ不能改原始文章喔><



像我就很可怕

你說的是3.14學長(方便稱呼的綽號

對不對XD


回亞硝酸學長:
小弟我其實沒有很強,如果真的很強也不會在 NPSC 和校內賽被電爆了QQ

謝謝學長寫的解題報告,不然我連自己在寫什麼都不知道...

n=100000 ?!? 好可怕~

回 ufve0704 學弟:

你加油!

你比我國一的時候還厲害喔

 


回3.14學弟:
沒關係還是很強<(_ _)>
不過你測資怎麼生的有點好奇(?)
然後在這裡繼續聊不太方便
或許可以私訊(?)

回ufve0704:
又一個電神OAO!?
怕爆wwwwwww




但我完全聽不懂DP.....

QAQ


我也不會DP QQ

HNO3 教嗎

 

<(_ _)>

 
#17964: Re:現在的學弟好可怕.........


88888888 (我討厭妙如)

School : 國立彰化女子高級中學
ID : 53135
IP address : [203.72.178.252]
Last Login :
2019-06-12 16:24:00
e217. 同分異構物(國二理化) -- π | From: [203.72.178.252] | Post Date : 2019-06-06 17:26

幹話區

為什麼現在的學弟都這麼可怕啦OAO
我記得我國中不會快速冪不會IO優化不會DP
而且這題是我上網爬很多文章才找到一個比較reasonable的做法
我是不是要輸光光啦><

還是有下面的題解其實沒有寫得很好...
如果有想提出意見的歡迎提出><

講這麼多其實只是想認識出題者XDD

Solution

這題以圖論角度來說就是給一個 $\ n$ ,求 $\ n$ 個節點,每個點度數不超過 $\ 4$ 的樹的數量。
我這個solution的大綱是:對於每個 $\ n$ 算出他的烷基數目,然後再算出烷類的數目。這兩個數字都可以用DP計算。


第一個步驟,定義 $\ a[i] $ 代表以 $\ i$ 個點構成烷基數量,在計算 $\ a[i]$ 時,
我們可以先選定一個根節點,然後選定不超過 $\ 3$ 個烷基當作他的子結點。
這裡是 $\ 3$ 個的原因是,烷基有一個lone pair(就是畫烷基時的那條沒有連接東西的線),
上面連一個碳度數就是 $\ 4$,我們這樣就可以方便的DP下去了。
這裡選定不超過 $\ 3$ 個子樹的做法就是類似01背包的做法,只是有一點要注意,
當要添加點數一樣是 $\ n$ 的子樹 $\ m$ 棵時方法數是 $\ H^{m}_{a[n]} $ 種 (而不是 $\ {a[n]}^{m} $ 種),至於為什麼就交給讀者吧(?)

第二個步驟其實跟第一個步驟很像,只是選 $\ 3$ 個變選 $\ 4$ 個,然後每次只能選大小不超過 $\ \frac{n}{2} $ 的烷基。
原因是,注意到每棵樹最多只有一個或兩個樹重心,而且如果有兩個樹重心必定由兩個大小為 $\ \frac{n}{2} $ 的樹的重心連接生成。
所以如果依照他們的樹重心枚舉,那每棵樹最多只會被算 $\ 1 $ 到 $\ 2 $ 次,
被算兩次就是剛剛說的有兩個樹重心的case,之後再扣掉就行了。

以上算法對每個 $\ n$ 複雜度是 $\ O(n^3)$ ,
不過其實在算 $\ n = 50$ 時就可以順便算出 $\ n = 1 ... 49$ 的答案了,所以總時間複雜度是 $\ O( C^3 + t) $,其中這題 $\ C=50, t=500$ 。

後記

我在查網路時有查到大陸這題有 $\ n = 100000$ 的...
據說要用生成函數+FFT+polya,感覺好可怕QQ

喔還有有人知道ZJ怎麼加 MathJax 嗎(?)


供三小


 
ZeroJudge Forum