多项式系数提取算法 c++

多项式系数提取算法可以使用杨辉三角（Pascal's Triangle）或者公式来实现。

1. 使用杨辉三角法

杨辉三角是一个三角形数字表，每个数字等于上面两个数字之和。可以使用杨辉三角来计算多项式系数。

例如，给定一个三次多项式 (a+b+c)^3，可以使用下面的杨辉三角来计算多项式系数。

          1
        1    1
      1    2    1
    1    3    3    1

每一行的数字都代表一个多项式的系数。例如，第四行的系数为 1 3 3 1，表示多项式 (a+b+c)^3 的系数。

C++代码实现：

vector<int> get_coefficients(int n) {
    vector<int> res(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        for (int j = i - 1; j >= 1; j--) {
            res[j] += res[j - 1];
        }
    }
    return res;
}

2. 使用公式法

多项式系数也可以使用公式来计算。公式如下：

C(n, k) = n! / (k! * (n - k)!)

其中，C(n, k) 表示从 n 个元素中选择 k 个元素的组合数。可以使用这个公式来计算多项式系数。

C++代码实现：

vector<int> get_coefficients(int n) {
    vector<int> res;
    for (int k = 0; k <= n; k++) {
        int c = 1;
        for (int i = 1; i <= k; i++) {
            c = c * (n - i + 1) / i;
        }
        res.push_back(c);
    }
    return res;
}

这个算法的时间复杂度为 O(n^2)。如果需要计算多个多项式的系数，可以预处理出一个杨辉三角或者使用动态规划来优化时间复杂度。