作者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/cn.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