你知道並查集（Disjoint-set Union）嗎？並查集是一種可以處理「快速合併兩個集合」並且詢問「某個元素所在的集合」這樣操作的資料結構。
具體來說，對於 N 個由 1 到 N 形成的集合 S = {{1}, {2}, . . . , {N}} ，並查集可以支援下列兩種操作：
1. 合併：指定 x 與 y ，合併元素 x 與元素 y 所屬的集合。
2. 查詢：指定 x 與 y ，查詢元素 x 與元素 y 是否同屬一個集合。
小 B 最近在演算法課程上學到了這個資料結構。專精隨機演算法的他，馬上開始好奇這個資料結構的「隨機」所需的執行週期（cycle）數。具體來說，在程式開始執行前，每個元素都在不同的集合。程式會花一個週期隨機選取 1 ≤ x < y ≤ N 並判斷 x 與 y 是否位於同一個集合。若 x 與 y 位於同個集合，則程式不做任何額外的事。若 x 與 y 分別位於集合 A 與集合 B，小 B 的程式會額外花 f(|A|, |B|) 個週期將集合 A 與集合 B 合併。這個過程會持續到所有元素都位於同一個集合為止。 小 B 想知道他的程式執行所需週期數的期望值，請你設計另一個程式幫幫他吧！
輸入第一行有一個正整數 N ，代表元素的個數。接著有 N 行，每行有 N 個非負整數，第 i 行的第 j 個代表 f(i, j)。
1. 保證 f(i, j) = f(j, i) 且對於所有 i + j > N ，不可能有合併大小 i 與 大小 j 的集合的操作，因此方便起見 f(i, j) = 0。
2. 1 ≤ N ≤ 40
3. 0 ≤ f(i, j) ≤ 109
輸出所需週期數的期望值。可以證明答案為有理數 P/Q ，為了避免浮點數誤差，請輸出 P × Q−1 (mod 109 + 7 )。其中 Q−1 為 Q 在模 109 +7 以下的乘法反元素 (亦可稱為模逆元)，也就是說 Q × Q−1 ≡ 1 (mod 109 + 7)。
#test input 1: 10 7 7 3 4 2 7 6 7 7 0 7 5 4 8 10 4 7 6 0 0 3 4 5 1 4 4 3 0 0 0 4 8 1 6 8 3 0 0 0 0 2 10 4 8 4 0 0 0 0 0 7 4 4 3 0 0 0 0 0 0 6 7 3 0 0 0 0 0 0 0 7 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 #test input 2: 2 1 0 0 0 #test input 3: 3 0 0 0 0 0 0 0 0 0 #test input 4: 1 0
#test input 1: 979356198 #test input 2: 2 #test input 3: 500000006 #test input 4: 0
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||