【PAT-Advanced】1009 Product of Polynomials

发表于 | 分类于 ， | | 阅读次数:

Problem

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}$

where $K$ is the number of nonzero terms in the polynomial, $N_i$ and $a_{N_i} (i=1,2,⋯,K)$ are the exponents and coefficients, respectively. It is given that $1≤K≤10$, $0≤N_K<⋯<N_2<N_1≤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.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6


Solution

Advanced-1002的升华版，要注意的是数组的上界，两个多项式的最高次分别可以是1000，则数组上界要开到2000。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

#define MAXN 2005
#define MAXK 15

double poly[MAXN];
int K1, K2;
int expo[MAXK], expo2;
double coe[MAXK], coe2;
int cnt = 0;
int first = -1;

void init(){
    for(int i=0; i<MAXN; i++){
        if(i<MAXK){
            expo[i] = 0;
            coe[i] = 0;
        }
        poly[i] = 0;
    }
}

int main(int argc, const char * argv[]) {
    init();
    cin >> K1;
    for(int i=0; i<K1; i++){
        cin >> expo[i] >> coe[i];
    }
    cin >> K2;
    for(int i=0; i<K2; i++){
        cin >> expo2 >> coe2;
        for(int j=0; j<K1; j++){
            poly[expo2+expo[j]] += coe2 * coe[j];
        }
    }
    for(int i=MAXN-1; i>=0; i--){
        if(poly[i] != 0){
            if(first == -1){
                first = i;
            }
            cnt ++;
        }
    }
    cout << cnt;
    for(int i=first; i>=0; i--){
        if(poly[i] != 0){
            cout << " " << i << " " << setiosflags(ios::fixed) << setprecision(1) << poly[i];
        }
    }
    cout << endl;
    return 0;
}