#P2553. [AHOI2001] 多项式乘法

    ID: 1561 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>向量快速傅里叶变换,FFT数论数学各省省选2001安徽

[AHOI2001] 多项式乘法

题目描述

请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算,特做以下约定:

  1. 代数多项式表达式中只涉及一个代数符号 a
  2. 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式,而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示,不得省略。
  3. 常数项以外的各项都是 xayxa^y 的形式,写作 xa^y,其中 xx 为该项的系数,而 yy 是该项的指数。x=1x = 1 时,不得简写成 a^y,应写成 1a^y。而 y=1y = 1 时,不得简写成 xa,应写成 xa^1

输入格式

文件中每行存放一个 可能含有乘法 的代数多项式表达式。若没有乘法,直接输出原式。输入中 可能出现不必要的空白字符

输出格式

每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后,指数相同的项必须合并同类项。不允许出现不必要的空白字符

(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)* (5a^1+1)
20a^3+17a^2+11a^1+2
25a^2+10a^1+1

提示

关于数据范围以及数据若干格式的说明:

  • 本题只有一组数据;
  • 保证每行的字符串没有任何空格;
  • 保证每行只有 至多 一个 * 符号(也即只有最多两个多项式相乘);
  • 保证 * 两侧的多项式都被刚好一对 () 括住。
  • 系数范围和指数范围均为 [0,30][0,30],不保证指数严格按照升序排列。