#22652: 解法思路


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [210.71.40.107]
最後登入時間 :
2024-03-29 10:41:11
b685. 5. 課堂抽籤 -- 2015高雄市資訊學科能力競賽高中組 | From: [220.137.35.125] | 發表日期 : 2020-09-22 23:34

老師指定抽籤號後,可能由 n 組變成 k 組,這 k組中有一種是 會有cycle的{整組的人皆已被指定抽籤號了}所以也不可能再和其它組合併了,假設有 c 組

另一種是整組中(含一人一組的)有一人是未被指定的{其實一組也只有一個人是未被指定} 假設有 z 組,z只要在輸入時計算 0 的個數即可

重點有二:(1)如何算出 c,建議用並查集,ai為0時z累加,ai不為0時 若 i及ai已是同一組則就是一個循環,將c累加
              (2)算出c,z後因為c組不可能再合併,所以等於 將 z 個 分成 m-c 組的方法數,可使用第一類 stirling數

請參考 https://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E6%9E%97%E6%95%B0

以S1(4,2)為例:共11種

1. (A,B) (C,D)

2. (A,C) (B,D)

3. (A,D) (B,C)

4. (A)   (B,C,D)

5. (A)   (B,D,C)

6. (B)   (A,C,D)

7. (B)   (A,D,C)

8. (C)   (A,B,D)

9. (C)   (A,D,B)

10.(D)   (A,B,C)

11.(D)   (A,C,B)

            即 s1(4,2)=11

遞推關係式: 無符號斯特林數有如下遞推關係式:

S1(n+1 , k) = n*[S1(n , k)] + S1(n,k-1) { for k>0 }

且初始為S1(0,0)=1, S1(n,0)=S1(0,n) = 0  { for n>0 }

 

 

 
ZeroJudge Forum