P2553 [AHOI2001] Polynomial Multiplication

Write a program to rewrite an algebraic polynomial expression that contains a multiplication operation into an algebraic polynomial without multiplication. To simplify the task, we make the following conventions: 1. The algebraic polynomial expression involves only one algebraic symbol `a`. 2. It is guaranteed that the input “algebraic polynomial with multiplication” contains exactly one multiplication between an “algebraic polynomial” and an “algebraic polynomial”. Formally, in each test, the input has exactly one line `(...)*(...)`, where `...` is an algebraic polynomial without multiplication. 3. An “algebraic polynomial without multiplication” is written as `XXXa^YYY+XXXa^YYY+XXXa^YYY+...+XXX` (representing $\text{XXX}a ^ \text{YYY} + \text{XXX}a ^ \text{YYY} + \text{XXX}a ^ \text{YYY} + \cdots + \text{XXX}$), where `XXX` and `YYY` are positive integers. Moreover, except for the first term, in each subsequent term the `YYY` is exactly $1$ less than that of the previous term. For example, a valid “algebraic polynomial without multiplication” is `142a^4+9a^3+4a^2+1a^1+3`. > For Convention 3, the original statement is: All non-constant terms are of the form $xa^y$, written as `xa^y`, where $x$ is the coefficient and $y$ is the exponent. When $x = 1$, it must not be abbreviated to `a^y`, and should be written as `1a^y`. When $y = 1$, it must not be abbreviated to `xa`, and should be written as `xa^1`.

The input consists of a single line string representing the given “algebraic polynomial with multiplication”. Its format is: `(...)*(...)`, where `...` is an algebraic polynomial without multiplication. For the constraints on “algebraic polynomial without multiplication,” refer to the Description.

Output a single string on one line representing the answer. Terms with larger exponents must not appear after terms with smaller exponents, and terms with the same exponent must be combined. No unnecessary whitespace characters are allowed. No parentheses are allowed in the output.

Notes on Constraints and some format details: - The ranges of coefficients and exponents are both $[0,30]$. Translated by ChatGPT 5