e217. 同分異構物(國二理化) -- π | From: [111.250.40.63] | 發表日期 : 2019-05-19 21:47

e217. 同分異構物(國二理化) -- π | From: [111.250.40.63] | 發表日期 : 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 嗎(?)

e217. 同分異構物(國二理化) -- π | From: [114.42.218.217] | 發表日期 : 2019-05-20 19:44

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

e217. 同分異構物(國二理化) -- π | From: [203.72.178.252] | 發表日期 : 2019-05-21 16:19

像我就很可怕

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

對不對XD

e217. 同分異構物(國二理化) -- π | From: [111.71.27.146] | 發表日期 : 2019-05-22 22:10

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

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

n=100000 ?!? 好可怕~

回 ufve0704 學弟:

你加油!

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

 

e217. 同分異構物(國二理化) -- π | From: [114.42.219.23] | 發表日期 : 2019-05-22 22:15

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

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

e217. 同分異構物(國二理化) -- π | From: [118.169.186.73] | 發表日期 : 2019-05-23 19:31

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

QAQ

e217. 同分異構物(國二理化) -- π | From: [203.72.178.252] | 發表日期 : 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 嗎(?)