PTT數位生活區 / C_and_CPP (C/C++)

[問題] 一個演算法的問題

看板C_and_CPP (C/C++)作者 (bravooooo)時間2年前 (2022/05/16 09:44), 編輯推噓6(6推 0噓 13→)
留言19則, 9人參與, 2年前最新討論串1/1
開發平台(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://www.ptt.cc/bbs/C_and_CPP/M.1652665484.A.4A8.html
推
05/16 10:15, 2年前 , 1F
可以去數學版問問
05/16 10:15, 1F
推
05/16 11:50, 2年前 , 2F
你的 (a1, a2,...,an) 和 (b1,b2,...bn) 是有規則的嗎？
05/16 11:50, 2F
→
05/16 13:02, 2年前 , 3F
沒有規則的哦 QQ
05/16 13:02, 3F
推
05/16 14:39, 2年前 , 4F
s domain model? 只能找通分後的係數規則了
05/16 14:39, 4F
→
05/16 14:54, 2年前 , 5F
Iteration的作法應該就是你說的暴力法? ((1,2)處理
05/16 14:54, 5F
→
05/16 14:54, 2年前 , 6F
後跟3) Divide and Conquer有用上了嗎? 會變O(logN)
05/16 14:54, 6F
推
05/16 15:17, 2年前 , 7F
bn是不是沒有單獨用到...?可以先把an*bn算一下?
05/16 15:17, 7F
→
05/16 16:04, 2年前 , 8F
更:D&C應無助益,因為s的最高次方在不同層的時候不同
05/16 16:04, 8F
→
05/16 16:44, 2年前 , 9F
應該是沒特別辦法 沒有規則又每一個都要算出來
05/16 16:44, 9F
推
05/16 16:46, 2年前 , 10F
大概就是把算過的先存起來 或考慮一些恆等式
05/16 16:46, 10F
推
05/16 17:39, 2年前 , 11F
能不能看看n=3的長相，也許很規律
05/16 17:39, 11F
→
05/16 18:18, 2年前 , 12F
直接算會太多嗎？an, bn 如果都整數用陣列存s多項式
05/16 18:18, 12F
→
05/16 18:18, 2年前 , 13F
分母部分直接乘或d&c來做大數乘法 假設結果為P ，
05/16 18:18, 13F
→
05/16 18:18, 2年前 , 14F
分子只需要在利用大數除法算出 sum ai * P/(1+aibis
05/16 18:18, 14F
→
05/16 18:18, 2年前 , 15F
) 這樣？
05/16 18:18, 15F
→
05/16 19:54, 2年前 , 16F
推薦個Prob_Solve板
05/16 19:54, 16F
→
05/17 02:35, 2年前 , 17F
然後分治應該做得到T(n)=2T(n/2)+O(多項式乘法)的複雜度吧
05/17 02:35, 17F
→
05/17 02:36, 2年前 , 18F
如果多項式乘法naive套個fft的話應該可以O(n log^2 n)?
05/17 02:36, 18F
→
05/17 02:36, 2年前 , 19F
(分母部分)
05/17 02:36, 19F
‣ 更多 bravooooo 的文章
文章代碼(AID): #1YWQoCIe (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bravooooo 的文章
文章代碼(AID): #1YWQoCIe (C_and_CPP)