目录

• [PAT Advanced Level] 1009 Product of Polynomials
• • 题目
  • 题解
  • 参考

[PAT Advanced Level] 1009 Product of Polynomials

题目

This time, you are supposed to find A×B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N 1 a N 1 N 2 a N 2 . . . N K a N K K N_1 a_{N1} N_2 a_{N2}...N_K a_{NK} KN1​aN1​N2​aN2​...NK​aNK​,where K is the number of nonzero terms in the polynomial, N i N_i Ni​ and a N i a_{N_i} aNi​​ ( i = 1 , 2 , ⋯ , K ) (i=1,2,⋯,K) (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤ N K N_K NK​ <⋯< N 2 N_2 N2​ < N 1 N_1 N1​ ≤1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

输入给出两组多项式A、B，求A*B。输入每一行，第一位为非零项的个数，后续分别为指数、系数、指数、系数。

示例

输入：
2 1 2.4 0 3.2
2 2 1.5 1 0.5

输出：
3 3 3.6 2 6.0 1 1.6
           

题解

先以结构体形式保存一组多项式的系数，指数由序号表示，然后输入第二组系数与第一组进行循环相乘，并加到对应指数的系数上，最后输出所有非零系数的项。

答案ans的系数数组至少要开到2001，因为两个最高次幂为1000的多项式相乘，最高幂次可以达到2000。

#include <cstdio>
struct Poly
{
    int exp;    //指数
    double cof;     //系数
} poly[1001];       //第一个多项式

double ans[2001];       //结果
int main()
{
    int n,m,number=0;
    scanf("%d",&n);     //第一个多项式中非零系数的项数
    for(int i=0;i<n;i++)
    {
        scanf("%d %lf",&poly[i].exp,&poly[i].cof);
    }
    scanf("%d",&m);     //第二个多项式中非零系数的项数
    for(int i=0;i<m;i++)
    {
        int exp;
        double cof;
        scanf("%d %lf",&exp,&cof);      //第二个多项式的指数和系数
        for(int j=0;j<n;j++)
        {
        ans[exp+poly[j].exp]+=(cof*poly[j].cof);
        }
    }
    for(int i=0;i<=2000;i++)
    {
        if(ans[i]!=0.0) number++;       //累计非零系数的项数
    }
    printf("%d",number);
    for(int i=2000;i>=0;i--)
    {
        if(ans[i]!=0.0)     printf(" %d %.1f",i,ans[i]);    //保留1位小数输出
    }
return 0;
}
           

参考

[算法笔记-上机训练实战指南-胡凡]