96台大工科離散最後一題

[joejoejoe (拎刀揮宿處)]

最近我朋友問我這題

(抱歉手上沒題目

題目大意是問以下字串

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
→ joejoejoe: 順帶一提這題15分
推 h04mp6286: 直覺是((15!)/(2!2!4!))*(C16 3)*(C19 3)
→ h04mp6286: 前面15!是除了"w"跟"."去做排列
→ h04mp6286: 後面是讓"w"跟"."去插入以排列好的字串間
→ h04mp6286: 有錯請見諒
推 h04mp6286: 少除一個2!應該是((15!)/(2!2!2!4!))*(C16 3)*(C19 3)
推 krusnoopy: http://i.imgur.com/3hioA0V.jpg
→ krusnoopy: 我會這麼做,也不知道對不對XD
推 h04mp6286: 最近頭很昏 請無視我下面那個少除一個二的推文 上面是
→ h04mp6286: 對的
噓 h04mp6286: 噓我自己 少看tw的"w"
→ h04mp6286: ((14!)/(2!2!4!))*(C15 3)*(C19 3)
→ krusnoopy: 樓上那個感覺會少算,插入第一次如果w相鄰,那後來再插入
→ krusnoopy: .在w中間也是皆不相鄰
推 h04mp6286: to krushsnoop大:那樣做好像只有考慮到wwww跟...全連起
→ h04mp6286: 來的有可能會漏掉"." ".."斷兩節以上的可能性
→ h04mp6286: 說的也是的確是少考慮到w.w的可能性
→ krusnoopy: 喔感謝,我誤會題目意思,以為是不全部在一起
→ joejoejoe: 這題有夠難，感覺考場遇到只能放棄。想說以防萬一問一
→ joejoejoe: 下好了，如果都沒有人會我就不管這題了
→ krusnoopy: 找一下歷屆詳解應該有,不過大概沒幾個學生會...
→ ken52011219: 好奇 @@ 但有題目嗎 為什麼連結連到台大而已QQ
→ krusnoopy: 題目就是台大網址去排列啦XDD
→ ken52011219: http://imgur.com/a/KlAzf 這題吧 ? 我算一下
→ ken52011219: 難在想不到更快速的方法去解他
→ ken52011219: 原本想用rock-polynomial fuction 去解
→ ken52011219: 但怎麼解出其中4*4 與 5*5的禁位多項式也是個問題
→ hypnos135g: 先考慮w和dot的順序再用插入的應該可解?
→ hypnos135g: w dot : 8!/4!4! 九個格子可插 x1+..+x9=11 其中x2..
→ hypnos135g: x8至少1
→ hypnos135g: 再乘剩下排列數 有bug嗎
→ hypnos135g: 有bug...當我沒說
→ hypnos135g: 考慮w dot外 11!/3!2!2! 考慮 w:c12取4 再考慮dot:c1
→ hypnos135g: 6取4 有bug嗎
→ joejoejoe: 有bug 你沒考慮都w.w跟.w.
→ Gabino: 先以"w"跟"."的排列情況來考慮 再把剩下的字元用重複組合
→ Gabino: 排進去空隙 然後再乘上排列數 最後再把所有case相加？
→ Gabino: 只不過第一階段的排列情況就有35種...
→ ken52011219: 我唯一想法只有(24x^4+96x^3+72x^2+16x+1)乘上
→ ken52011219: 120x^5+600x^4+600x^3+200x^2+25x^1+1
→ ken52011219: 套上亂序公式得解，不然這題純排容會做到天荒地老
→ joejoejoe: 感覺沒有更好的做法了，感謝ken大的幫忙