Research Space for Linear Algebra & Discrete Mathematics
你題目好像記錯了~用rook polynomial可以秒殺請參考 http://zjhwang.blogspot.com/2009/12/2.html
數據忘記了... 只記得題意感謝回答 ^^
題目應該是這樣四女 五男女1不配男1,3,5女2不配男2,4女3不配男3,5女4不配男4請問root該怎麼做呢?不大清楚
這題可用rook、排容、tree、暴力法解，個人當時實際操作是以tree最快，因為女1已經限制不和1,3,5了，所以只有兩種可能(2,4)。tree只花了2分鐘..就得15分= =不過rook應該也會很快
暴力法還可以算的出來我用 pai 記的版本寫一下這題用rook polynomial來算的方法, 細節部分請參考╰(〒皿〒)╯幫忙轉的那一篇假設 row i 是女i, column j 代表男j, 一開始畫出來的禁位表長這樣: 一 二 三 四 五1 |ｘ| |ｘ| |ｘ|2 | |ｘ| |ｘ| |3 | | |ｘ| |ｘ|4 | | | |ｘ| |適當的調換列、行, 把 ｘ 集中到若干個 blocks: 一 三 五 二 四1 |ｘ|ｘ|ｘ| | |3 | |ｘ|ｘ| | |2 | | | |ｘ|ｘ|4 | | | | |ｘ|左上角 r(C1,x) = 1 + 5x + 4x^2右下角 r(C2,x) = 1 + 3x + x^2r(C,x) = r(C1,x)r(C2,x)= 1 + 8x + 20x^2 + 17x^3 + 4x^4所以總數就是(5*4*3*2) - 8*(4*3*2) + 20*(3*2) - 17*2 + 4 = 18
天哪...我用排容還算錯...成大消失了
感謝助教回答 ^^
張貼留言
7 則留言:
你題目好像記錯了~
用rook polynomial可以秒殺
請參考 http://zjhwang.blogspot.com/2009/12/2.html
數據忘記了... 只記得題意
感謝回答 ^^
題目應該是這樣
四女 五男
女1不配男1,3,5
女2不配男2,4
女3不配男3,5
女4不配男4
請問root該怎麼做呢?不大清楚
這題可用rook、排容、tree、暴力法解，
個人當時實際操作是以tree最快，因為女1已經限制不和1,3,5了，所以只有兩種可能(2,4)。tree只花了2分鐘..就得15分= =
不過rook應該也會很快
暴力法還可以算的出來
我用 pai 記的版本寫一下這題用rook polynomial來算的方法, 細節部分請參考╰(〒皿〒)╯幫忙轉的那一篇
假設 row i 是女i, column j 代表男j,
一開始畫出來的禁位表長這樣:
一 二 三 四 五
1 |ｘ| |ｘ| |ｘ|
2 | |ｘ| |ｘ| |
3 | | |ｘ| |ｘ|
4 | | | |ｘ| |
適當的調換列、行, 把 ｘ 集中到若干個 blocks:
一 三 五 二 四
1 |ｘ|ｘ|ｘ| | |
3 | |ｘ|ｘ| | |
2 | | | |ｘ|ｘ|
4 | | | | |ｘ|
左上角 r(C1,x) = 1 + 5x + 4x^2
右下角 r(C2,x) = 1 + 3x + x^2
r(C,x) = r(C1,x)r(C2,x)
= 1 + 8x + 20x^2 + 17x^3 + 4x^4
所以總數就是
(5*4*3*2) - 8*(4*3*2) + 20*(3*2) - 17*2 + 4 = 18
天哪...我用排容還算錯...成大消失了
感謝助教回答 ^^
張貼留言