96台大工科離散最後一題

看板Grad-ProbAsk作者 (拎刀揮宿處)時間8年前 (2017/01/22 10:54), 編輯推噓4(5推 1噓 36→)
留言42則, 6人參與, 最新討論串1/1
最近我朋友問我這題 (抱歉手上沒題目 題目大意是問以下字串 http://www.ntu.edu.tw "w"不相鄰且 " . "不相鄰 之可能排列數 直覺是用排容，但交集不會求 請問有人會嗎？ ----- Sent from JPTT on my HTC_D626x. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.198.44.49 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485053673.A.2D0.html
→
01/22 10:55, , 1F
順帶一提這題15分
01/22 10:55, 1F
推
01/22 11:15, , 2F
直覺是((15!)/(2!2!4!))*(C16 3)*(C19 3)
01/22 11:15, 2F
→
01/22 11:16, , 3F
前面15!是除了"w"跟"."去做排列
01/22 11:16, 3F
→
01/22 11:17, , 4F
後面是讓"w"跟"."去插入以排列好的字串間
01/22 11:17, 4F
→
01/22 11:18, , 5F
有錯請見諒
01/22 11:18, 5F
推
01/22 11:24, , 6F
少除一個2!應該是((15!)/(2!2!2!4!))*(C16 3)*(C19 3)
01/22 11:24, 6F
推
01/22 11:29, , 7F
01/22 11:29, 7F
→
01/22 11:30, , 8F
我會這麼做,也不知道對不對XD
01/22 11:30, 8F
推
01/22 11:31, , 9F
最近頭很昏 請無視我下面那個少除一個二的推文 上面是
01/22 11:31, 9F
→
01/22 11:31, , 10F
對的
01/22 11:31, 10F
噓
01/22 11:36, , 11F
噓我自己 少看tw的"w"
01/22 11:36, 11F
→
01/22 11:37, , 12F
((14!)/(2!2!4!))*(C15 3)*(C19 3)
01/22 11:37, 12F
→
01/22 11:38, , 13F
樓上那個感覺會少算,插入第一次如果w相鄰,那後來再插入
01/22 11:38, 13F
→
01/22 11:38, , 14F
.在w中間也是皆不相鄰
01/22 11:38, 14F
推
01/22 11:40, , 15F
to krushsnoop大:那樣做好像只有考慮到wwww跟...全連起
01/22 11:40, 15F
→
01/22 11:40, , 16F
來的有可能會漏掉"." ".."斷兩節以上的可能性
01/22 11:40, 16F
→
01/22 11:41, , 17F
說的也是的確是少考慮到w.w的可能性
01/22 11:41, 17F
→
01/22 11:41, , 18F
喔感謝,我誤會題目意思,以為是不全部在一起
01/22 11:41, 18F
→
01/22 12:02, , 19F
這題有夠難，感覺考場遇到只能放棄。想說以防萬一問一
01/22 12:02, 19F
→
01/22 12:02, , 20F
下好了，如果都沒有人會我就不管這題了
01/22 12:02, 20F
→
01/22 12:05, , 21F
找一下歷屆詳解應該有,不過大概沒幾個學生會...
01/22 12:05, 21F
→
01/22 12:09, , 22F
好奇 @@ 但有題目嗎 為什麼連結連到台大而已QQ
01/22 12:09, 22F
→
01/22 12:11, , 23F
題目就是台大網址去排列啦XDD
01/22 12:11, 23F
→
01/22 12:12, , 24F
http://imgur.com/a/KlAzf 這題吧 ? 我算一下
01/22 12:12, 24F
→
01/22 12:46, , 25F
難在想不到更快速的方法去解他
01/22 12:46, 25F
→
01/22 12:47, , 26F
原本想用rock-polynomial fuction 去解
01/22 12:47, 26F
→
01/22 12:48, , 27F
但怎麼解出其中4*4 與 5*5的禁位多項式也是個問題
01/22 12:48, 27F
→
01/22 13:44, , 28F
先考慮w和dot的順序再用插入的應該可解?
01/22 13:44, 28F
→
01/22 13:46, , 29F
w dot : 8!/4!4! 九個格子可插 x1+..+x9=11 其中x2..
01/22 13:46, 29F
→
01/22 13:46, , 30F
x8至少1
01/22 13:46, 30F
→
01/22 13:51, , 31F
再乘剩下排列數 有bug嗎
01/22 13:51, 31F
→
01/22 14:11, , 32F
有bug...當我沒說
01/22 14:11, 32F
→
01/22 14:26, , 33F
考慮w dot外 11!/3!2!2! 考慮 w:c12取4 再考慮dot:c1
01/22 14:26, 33F
→
01/22 14:26, , 34F
6取4 有bug嗎
01/22 14:26, 34F
→
01/22 18:27, , 35F
有bug 你沒考慮都w.w跟.w.
01/22 18:27, 35F
→
01/22 19:00, , 36F
先以"w"跟"."的排列情況來考慮 再把剩下的字元用重複組合
01/22 19:00, 36F
→
01/22 19:00, , 37F
排進去空隙 然後再乘上排列數 最後再把所有case相加？
01/22 19:00, 37F
→
01/22 19:00, , 38F
只不過第一階段的排列情況就有35種...
01/22 19:00, 38F
→
01/22 19:03, , 39F
我唯一想法只有(24x^4+96x^3+72x^2+16x+1)乘上
01/22 19:03, 39F
→
01/22 19:05, , 40F
120x^5+600x^4+600x^3+200x^2+25x^1+1
01/22 19:05, 40F
→
01/22 19:06, , 41F
套上亂序公式得解，不然這題純排容會做到天荒地老
01/22 19:06, 41F
→
01/22 22:43, , 42F
感覺沒有更好的做法了，感謝ken大的幫忙
01/22 22:43, 42F
‣ 更多 joejoejoe 的文章
文章代碼(AID): #1OX1xfBG (Grad-ProbAsk)