[C++知识库]浙江大学软件学院 2020 年保研机考 7-1 Standard Form of Polynomial (C++)

The standard form of a polynomial of degree $n$ is $P(x)=a_n{x}_n+a_{n?1}{x}_{n?1}+?+a_{1}x+a_0$. Given that $a_n=1$ and all the $n$ roots $r_1,...,r_n$ of $P(x)$ are integers. Then $P(x)$ can be written as $(x?r_1)(x?r_2)?(x?r_n)$. Your job is to write $P(x)$ in its standard form with all roots given.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive $n(\le 10)$ which is the degree of $P(x)$. Then n integer roots are given in the next line, separated by spaces.

Output Specification:

For each case, output the coefficients $a_i(i=n?1,?,0)$ in a line. All the numbers must be separated by one space, and there must be no extra space at the beginning or the end of the line. It is guaranteed that all the calculation will be within the range of int.

Sample Input:

3
-1 4 -1

Sample Output:

-2 -7 -4

Solution:

// Talk is cheap, show me the code
// Created by Misdirection 2021-09-19 13:12:52
// All rights reserved.

#include <iostream>
#include <vector>

using namespace std;

int roots[15];
int coeff[15];
int tmp[15];

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; ++i) scanf("%d", &roots[i]);
    for(int i = 0; i < n; ++i) roots[i] = -roots[i];

    coeff[1] = 1;
    coeff[0] = roots[0];

    for(int i = 1; i < n; ++i){
        for(int j = 0; j <= i; ++j) tmp[j] = coeff[j];

        for(int j = i + 1; j > 0; --j) coeff[j] = coeff[j - 1];
        coeff[0] = 0;

        for(int j = 0; j <= i; ++j) coeff[j] += roots[i] * tmp[j];

    }

    for(int i = n - 1; i >= 0; --i){
        if(i == 0) printf("%d\n", coeff[i]);
        else printf("%d ", coeff[i]);
    }

    return 0;
}