如何找到多項式中x^m的係數？

x^m (m<=n)

係數類型

(a1+b1x)(a2+b2x)...(an+bnx)? O(n^2)

的多項式算法所需

！

2014-10-08 arjun8012

這個問題似乎是題外話，因爲它是關於純數學，而不是編程問題。 – recursive 2014-10-08 03:35:43

純粹的數學方法並不總是適合這個問題，因爲n！複雜性對於相當大的尺寸輸入是不真實的，所以需要最優算法 – MBo 2014-10-08 08:45:41

那麼問題是關於在可行時間複雜度下計算所需答案的動態規劃解決方案。每個係數都不能用筆和紙來計算。因此，必須有一些方法來使過程自動化。 – arjun8012 2014-10-08 11:47:51

(a1+b1x)(a2+b2x)...(an+bnx)=b1*b2*...*bn*(a1/b1+x)*(a2/b2+x)...(a/bn+x)

右側部分多項式的根（-a1/B1，〜A2/B2的...-/BN）

有O（N^2）的算法來查找這個多項式的係數，實現here

（不要忘記b的產品倍增係數[1]）

2014-10-08 05:27:29 MBo

親自說說我會用二項式定理的歸納應用。

這將解決兩個二項式你的基本情況。然後剩下的就是使用乘法的相關性重複應用程序。

雖然我不太瞭解C，但我很抱歉。

2014-10-08 03:36:59

m個元素的係數爲0和m使得恰好有的bm選擇（和an - m選擇）之間的所有i的(a or b)[i]所有可能的乘積的和。

更多程序上，generate所有combinations整數0和m之間，這些索引相乘的a元素，獲得每個組合的complement和通過的b這些索引的元素進一步相乘所獲得的產物。一起添加所有獲得的產品。

2014-10-08 03:46:53 Amadan

回答