A1009. 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 N1 aN1 N2 aN2 ... NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < ... < N2 < 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.
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
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int K, n, count = ;
double a, poly1[] = {}, re[] = {};
scanf("%d", &K);
for(int i = ; i < K; i++){
scanf("%d%lf", &n, &a);
poly1[n] = a;
}
scanf("%d", &K);
for(int i = ; i < K; i++){
scanf("%d%lf", &n, &a);
for(int j = ; j < ; j++)
re[n + j] = re[n + j] + poly1[j] * a;
}
for(int i = ; i >= ; i--){
if(re[i] != )
count++;
}
printf("%d", count);
for(int i = ; i >= ; i--){
if(re[i] != )
printf(" %d %.1lf", i, re[i]);
}
cin >> K;
return ;
}
总结:
1、指数为1000的多项式乘法,结果最高为2000次幂。
2、为减少时间复杂度,可以将第一个多项式存储,第二个不存。第二个多项式边读入边直接遍历poly1并做乘法。还可以将两个多项式的系数与指数分别开数组存下来以减小复杂度。
最新文章
- 第二章作业-第3题(markdown格式)-万世想
- 解决报错 ora-00704 ora-00604 ora-00942 启动不了数据库问题
- CSS基本知识1-CSS基本概念
- paper 114:Mahalanobis Distance(马氏距离)
- HTML5获取地理位置
- linux修改ip地址的方法
- php在centos下的脚本没有解析的问题
- C10K问题渣翻译
- CoInitialize()、CoInitializeEx()和AfxOleInit()区别联系
- Android-xUtils框架介绍(四)
- Android 模拟HTTP协议的编码问题 Android默认编码UTF-8
- ECshop 表结构
- jquery调用wcf案例
- linux之ls -l|grep ";^-";|wc -l命令
- JSP和El表达式和JSTL标签库使用
- continous integration environment (Jenkins and bitbucket configuration)
- 开发环境MAPLAB下使用仿真器ICD2程序下载流程
- 微信原始demo
- python常见的报错提示
- vmware彻底隐藏控制栏白条