作者bravooooo (bravooooo)
看板C_and_CPP
標題[問題] 一個演算法的問題
時間Mon May 16 09:44:42 2022
開發平台(Platform): (Ex: Win10, Linux, ...)
ubuntu 12.x
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
g++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question)：
大家好 最近遇到一個演算法的問題
題目是要求解 a1/(1+a1*b1*s) + a2/(1+a2*b2*s)... + an/(1+an*bn*s)
加總後的各個係數
以2項為例就是:
a1/(1+a1*b1*s) + a2/(1+a2*b2*s) =
分母通分 → [a1(1+a2*b2) + a2(1+a1*b1)] *s / (1+a1*b1*s)(1+a2*b2*s) =
[a1(1+a2*b2) + a2(1+a1*b1)] *s / [1 +
(a1*b1+a2*b2)s +
(a1*b1*a2*b2)s^2]
上式中黃色部份即為所求
題目的多項式用暴力展開可以得到分母部份可以用組合公式把每一項求出
但若 n的值太大組合數會超多 計算量也跟著爆炸
不知道像這種題目有沒有什麼更好的解法呢
述敘的有點亂請大家見諒 也謝謝大家幫忙 Q_Q
餵入的資料(Input)：
預期的正確結果(Expected Output)：
錯誤結果(Wrong Output)：
程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
補充說明(Supplement)：
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.131.156 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1652665484.A.4A8.html
1F：推 j0958322080: 可以去數學版問問 05/16 10:15
2F：推 closer76: 你的 (a1, a2,...,an) 和 (b1,b2,...bn) 是有規則的嗎？ 05/16 11:50
3F：→ bravooooo: 沒有規則的哦 QQ 05/16 13:02
4F：推 hongsiangfu: s domain model? 只能找通分後的係數規則了 05/16 14:39
5F：→ jack7775kimo: Iteration的作法應該就是你說的暴力法? ((1,2)處理 05/16 14:54
6F：→ jack7775kimo: 後跟3) Divide and Conquer有用上了嗎? 會變O(logN) 05/16 14:54
7F：推 TheOneisNEO: bn是不是沒有單獨用到...?可以先把an*bn算一下? 05/16 15:17
8F：→ jack7775kimo: 更:D&C應無助益,因為s的最高次方在不同層的時候不同 05/16 16:04
9F：→ TheOneisNEO: 應該是沒特別辦法 沒有規則又每一個都要算出來 05/16 16:44
10F：推 TheOneisNEO: 大概就是把算過的先存起來 或考慮一些恆等式 05/16 16:46
11F：推 hellophoenix: 能不能看看n=3的長相，也許很規律 05/16 17:39
12F：→ mikemike1021: 直接算會太多嗎？an, bn 如果都整數用陣列存s多項式 05/16 18:18
13F：→ mikemike1021: 分母部分直接乘或d&c來做大數乘法 假設結果為P ， 05/16 18:18
14F：→ mikemike1021: 分子只需要在利用大數除法算出 sum ai * P/(1+aibis 05/16 18:18
15F：→ mikemike1021: ) 這樣？ 05/16 18:18
16F：→ oToToT: 推薦個Prob_Solve板 05/16 19:54
17F：→ oToToT: 然後分治應該做得到T(n)=2T(n/2)+O(多項式乘法)的複雜度吧 05/17 02:35
18F：→ oToToT: 如果多項式乘法naive套個fft的話應該可以O(n log^2 n)? 05/17 02:36
19F：→ oToToT: (分母部分) 05/17 02:36